递归遍历

先序遍历

144. 二叉树的前序遍历

问题

【LeetCode 144】：给你二叉树的根节点 root ，返回它节点值的 前序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> ans = new ArrayList<>();
    preorder(root, ans);
    return ans;
}

public void preorder(TreeNode root, List<Integer> res) {

  if (root == null) {
      return;
  }
  res.add(root.val);
  preorder(root.left, res);
  preorder(root.right, res);
}

中序遍历

94. 二叉树的中序遍历

问题

【LeetCode 94】：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> inorderTraversal(TreeNode root) {

  List<Integer> ans = new ArrayList<>();
  inorder(root, ans);
  return ans;
}

public void inorder(TreeNode root, List<Integer> ans) {

  if (root == null) {
      return;
  }
  inorder(root.left, ans);
  ans.add(root.val);
  inorder(root.right, ans);
}

后序遍历

145. 二叉树的后序遍历

问题

【LeetCode 145】：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> postorderTraversal(TreeNode root) {
  
  List<Integer> ans = new ArrayList<>();
  postorder(root, ans);
  return ans;
}

public void postorder(TreeNode root, List<Integer> ans) {
  
  if (root == null) {
      return;
  }
  postorder(root.left, ans);
  postorder(root.right, ans);
  ans.add(root.val);
}

迭代遍历

前序遍历

144. 二叉树的前序遍历 

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
public List<Integer> preorderTraversal(TreeNode head) {

  // res
  List<Integer> res = new ArrayList<>();
  if (head != null) {
      // 定义辅助栈
      Stack<TreeNode> stack = new Stack<>();
      // 根节点入栈
      stack.add(head);

      // 先访问根节点，再访问左子树，然后访问右子树
      while (!stack.isEmpty()) {
          // 弹出栈顶一个节点
          head = stack.pop();
          res.add(head.val);
          // 先入栈该节点的右孩子 （栈的先进后出性质）
          if (head.right != null) {
              stack.push(head.right);
          }
          // 再入栈该节点的左孩子
          if (head.left != null) {
              stack.push(head.left);
          }
      }
  }
  return res;
}

中序遍历

94. 二叉树的中序遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> inorderTraversal(TreeNode head) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    if (head == null) {
        return ans;
    }

    while (!stack.isEmpty() || head != null) {
        // 一直往左分支走
        while (head != null) {
            stack.push(head);
            head = head.left;
        }

        if (!stack.isEmpty()) {
            head = stack.pop();
            ans.add(head.val); // Visit(head)
            // 转向右分支
            head = head.right;
        }
    }
    return ans;
}

后序遍历

145. 二叉树的后序遍历 

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
// 逆先序
// 先序遍历非递归版本进栈顺序是：根右左
// 后序遍历非递归版本采用双栈，进栈顺序是：根左右
public List<Integer> postorderTraversal(TreeNode head) {

    List<Integer> res = new ArrayList<>();

    if (head != null) {
        // 输入栈
        Stack<TreeNode> in = new Stack<>();
        // 输出栈
        Stack<TreeNode> out = new Stack<>();

        // 将根节点放入输入栈
        in.push(head);

        while (!in.isEmpty()) {

            // 从输入栈取出栈顶元素放入输出栈中
            head = in.pop();
            out.push(head);

            // 先 左
            if (head.left != null) {
                in.push(head.left);
            }

            // 后 右
            if (head.right != null) {
                in.push(head.right);
            }
        }

        // 输出
        while (!out.isEmpty()) {
            res.add(out.pop().val);
        }
    }
    return res;
}