一、递归方式遍历

直接贴

1
2
3
4
5
6
7

void traverse(TreeNode root) {
    // 前序遍历代码位置
    traverse(root.left);
    // 中序遍历代码位置
    traverse(root.right);
    // 后序遍历代码位置
}

二、迭代方式遍历

1. 先序遍历

没什么好说的，递归改成迭代直接使用栈数据结构，先序遍历的代码比较简单。

  1. root节点出栈，top节点
  2. 自己的处理代码
  3. root.right和root.left依次入栈，循环直到栈为空
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public static void preOrderIteration(TreeNode head) {
	if (head == null) {
		return;
	}
	ArrayDeque<TreeNode> stack = new ArrayDeque<>();
	stack.push(head);
	while (!stack.isEmpty()) {
		TreeNode node = stack.pop();
		// System.out.print(node.val + " ");
         // 前序遍历代码位置
		if (node.right != null) {
			stack.push(node.right);
		}
		if (node.left != null) {
			stack.push(node.left);
		}
	}
}

public static void preorderTraversal(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                // System.out.print(node.val + " ");
                // 前序遍历代码位置
                stack.push(cur);
                cur = cur.left; //考虑左子树
            }else {
                //节点为空，就出栈
                cur = stack.pop();
                //考虑右子树
                cur = cur.right;
            }
        }
}

2. 中序遍历

94. Binary Tree Inorder Traversal

具体例子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


        1
      /   \
     2     3
    / \   /
   4   5 6

 push   push   push   pop     pop    push     pop     pop 
|   |  |   |  |_4_|  |   |   |   |  |   |    |   |   |   |  
|   |  |_2_|  |_2_|  |_2_|   |   |  |_5_|    |   |   |   |
|_1_|  |_1_|  |_1_|  |_1_|   |_1_|  |_1_|    |_1_|   |   |
ans                  add 4   add 2           add 5   add 1
[]                   [4]     [4 2]           [4 2 5] [4 2 5 1]
 push   push   pop          pop 
|   |  |   |  |   |        |   |  
|   |  |_6_|  |   |        |   |  
|_3_|  |_3_|  |_3_|        |   |
              add 6        add 3
              [4 2 5 1 6]  [4 2 5 1 6 3]


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public static void inorderTraversal(TreeNode root) {
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        // System.out.print(node.val + " ");
        // 中序遍历代码位置
        cur = node.right;
    }
}

public List<Integer> inorderTraversal(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                // System.out.print(node.val + " ");
                // 中序遍历代码位置
                list.add(node.val);
                cur = node.right;
            }
        }
        return list;
    }

3. 后序遍历

主要就是用栈要模拟递归的过程，区别于之前 94 题 中序遍历和 144 题 先序遍历，后序遍历的非递归形式会相对难一些。

原因就是，当遍历完某个根节点的左子树，回到根节点的时候，对于中序遍历和先序遍历可以把当前根节点从栈里弹出，然后转到右子树。举个例子，

image-20211029113931122

如何判断是从左子树到的根节点还是从右子树到的根节点？

  1. 利用set 数据结构来判断经过的次数
  2. 判断当前节点的右子节点与上一次遍历节点相同
  3. 同一节点两次进栈

1、2 思想是一致的，但是代码实现不同。

同一节点两次进栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static void postorderTraversal(TreeNode root) {
    if (root == null)
        return;
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        if (!stack.isEmpty() && cur == stack.peek()) {
            if (cur.right != null) {
                stack.push(cur.right);
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
                stack.push(cur.left);
            }
        } else {
            // System.out.println(cur.val);
            // 后序遍历代码
        }
    }
}

判断当前节点的右子节点与上一次遍历节点相同

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public static void postorderTraversal(TreeNode root) {
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    TreeNode prev = null;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            TreeNode temp = stack.peek();
            if (temp.right != null && temp.right != prev) {
                cur = temp.right;
            } else {
                // System.out.println(cur.val);
                // 后序遍历代码
                prev = temp;
                stack.pop();
            }
        }
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> st = new LinkedList<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null || !st.isEmpty()) {
            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                cur = st.peek();
                if (cur.right == null || cur.right == pre) {
                    pre = st.pop();
                    res.add(cur.val);
                    cur = null;
                } else {
                    cur = cur.right;
                }
            }
        }
        return res;
    }
}