一.前序遍历

1.递归

    ArrayList list = new ArrayList<>();public List preorderTraversal(TreeNode root) {preOrder(root);return list;}public void preOrder(TreeNode root) {if (root != null) {list.add(root.val);preOrder(root.left);preOrder(root.right);}}

2.栈迭代

在进行使用栈进行迭代的时候,我们是先入栈右节点,然后入栈左节点,这样做是和栈的结构进行匹配的,因为栈是先进后出的结构,所以先入栈右节点,再入栈左节点,这样出栈的时候左节点才能先出栈

第一次:先入栈1,stack={1}

第二次:然后出栈1,入栈1的右节点3,stack={3},入栈1的左节点2 stack={3,2}

第三次:出栈顶元素2,stack={3},入栈2的右节点,入栈2的左节点.stack={3,5,4}

第四次,出栈顶元素4,stack={3,5},入栈4的左节点6,stack={3,5,6};

第五次:出栈顶元素6,左右结点都为空,没有元素入栈,stack={3,5};

第六次:出栈顶元素5,入栈5的右节点7,stack={3,7};

第七次:出栈顶元素7,,没有元素入栈,stack={3};

第八次,出栈顶元素3,没有元素入栈,stack={};迭代结束

   //入栈顺序为,中-->右-->左public static List preorderTraversal(TreeNode root) {LinkedList stack = new LinkedList<>();List res = new ArrayList<>();if (root == null) {return res;}stack.push(root);while (!stack.isEmpty()) {TreeNode pop = stack.pop();res.add(pop.val);if (pop.right != null) {stack.push(pop.right);}if (pop.left != null) {stack.push(pop.left);}}return res;}

3.Morris遍历

Morris遍历利用了树的线索化,时间复杂度为O(n)，空间复杂度为O(1),主要节省了空间,时间复杂度还是不变,具体的分析请看这篇文章:树的前中后序的Morris遍历_允歆辰丶的博客-CSDN博客,这里直接给出代码:

    public List preorderTraversal(TreeNode root) {List res = new ArrayList<>();TreeNode curr = root;while (curr != null) {if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);curr = curr.right;} else {// 找到当前节点的前驱节点TreeNode prev = curr.left;while (prev.right != null && prev.right != curr) {prev = prev.right;}if (prev.right == null) {res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);// 将前驱节点的右子树连接到当前节点prev.right = curr;curr = curr.left;} else {// 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树prev.right = null;curr = curr.right;}}}return res;}

二.中序遍历

1.递归

    ArrayList list = new ArrayList<>();public List inorderTraversal(TreeNode root) {infixOrder(root);return list;}public void infixOrder(TreeNode root) {if (root != null) {infixOrder(root.left);list.add(root.val);infixOrder(root.right);}}

2.栈迭代

    //入栈顺序： 左-右public static List inorderTraversal(TreeNode root) {List res = new ArrayList<>();if (root == null) {return res;}LinkedList stack = new LinkedList<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {//cur不为空,说明没有遍历到最左端的叶子结点,也就是第一个输出的结点stack.push(cur);cur = cur.left;} else {cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}

3.Morris遍历

 具体的分析请看这篇文章:树的前中后序的Morris遍历_允歆辰丶的博客-CSDN博客,这里直接给出代码:

public class InorderThreadedBinaryTree {private ThreadTreeNode pre = null;public void threadedNodes(ThreadTreeNode node) {//如果node==null，不能线索化if (node == null) {return;}//1、先线索化左子树threadedNodes(node.left);//2、线索化当前结点//处理当前结点的前驱结点//以8为例来理解//8结点的.left = null，8结点的.leftType = 1if (node.left == null) {//让当前结点的左指针指向前驱结点node.left = pre;//修改当前结点的左指针的类型，指向前驱结点node.leftType = 1;}//处理后继结点if (pre != null && pre.right == null) {//让当前结点的右指针指向当前结点pre.right = node;//修改当前结点的右指针的类型=pre.rightType = 1;}//每处理一个结点后，让当前结点是下一个结点的前驱结点pre = node;//3、线索化右子树threadedNodes(node.right);}}class ThreadTreeNode {int val;ThreadTreeNode left;//0为非线索化,1为线索化int leftType;ThreadTreeNode right;//0为非线索化,1为线索化int rightType;public ThreadTreeNode(int val) {this.val = val;}
}

三.后序遍历

1.递归

    ArrayList list = new ArrayList<>();public List postorderTraversal(TreeNode root) {postOrder(root);return list;}public void postOrder(TreeNode root) {if (root != null) {postOrder(root.left);postOrder(root.right);list.add(root.val);}}

2.栈迭代

    入栈顺序：中-->左-->右 出栈顺序：中-->右-->左public List postorderTraversal(TreeNode root) {List res = new ArrayList<>();if (root == null) {return res;}LinkedList stack = new LinkedList<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();res.add(node.val);if (node.left != null) {stack.push(node.left);}if (node.right != null) {stack.push(node.right);}}Collections.reverse(res);return res;}

3.Morris遍历

 具体的分析请看这篇文章:树的前中后序的Morris遍历_允歆辰丶的博客-CSDN博客,这里直接给出代码:

    public List postorderTraversal(TreeNode root) {List res = new ArrayList<>();TreeNode dump = new TreeNode(0);//建立一个临时结点dump.left = root;  //设置dump的左节点为rootTreeNode curr = dump;  //当前节点为dumpwhile (curr != null) {if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树curr = curr.right;} else {// 找到当前节点的前驱节点TreeNode prev = curr.left;while (prev.right != null && prev.right != curr) {prev = prev.right;}if (prev.right == null) {// 将前驱节点的右子树连接到当前节点prev.right = curr;curr = curr.left;} else {reverseAddNodes(curr.left, prev, res);// 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树prev.right = null;curr = curr.right;}}}return res;}private void reverseAddNodes(TreeNode begin, TreeNode end, List res) {reverseNodes(begin, end); //将begin到end的进行逆序连接TreeNode curr = end;while (true) {//将逆序连接后端begin到end添加res.add(curr.val);if (curr == begin)break;curr = curr.right;}reverseNodes(end, begin);//恢复之前的连接状态}/*** 将begin到end的进行逆序连接** @param begin* @param end*/private void reverseNodes(TreeNode begin, TreeNode end) {TreeNode prev = begin;TreeNode curr = prev.right;TreeNode post;while (prev != end) {post = curr.right;curr.right = prev;prev = curr;curr = post;}}

四.层序遍历

1.队列迭代

层序遍历主要是利用了队列先进后出的性质,每一次的循环次数为为当前层的结点的个数,在遍历的当前层的结点的同时,如果左右孩子不为空的话,入队当前结点的左右孩子结点,直到队列里面没有元素.例如:

第一次先根结点入队列:queue={1};

第二次:1结点出队列,然后将1的左右节点2结点和3结点入队列,queue={2,3};

第三次:2结点出队列,4和5结点入队列,3出队列,3无左右节点,queue={4,5};

第四次:4结点出队列,4的左节点入队列,5结点出队列,5的右节点入队列,queue={6,7}

第五次,6,7结点出队列,因为他们都没有左右节点,因此queue=null,遍历结束

    public List> levelOrder(TreeNode root) {List> list = new ArrayList<>();if (root == null)return list;LinkedList queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List res = new ArrayList<>();for (int i = 0; i < size; ++i) {TreeNode node = queue.poll();res.add(node.val);if (node.left != null)queue.offer(node.left);if (node.right != null)queue.offer(node.right);}list.add(res);}return list;}