vlambda博客
学习文章列表

  二叉树的遍历一般有四种：先序遍历（前序）、中序遍历、后序遍历和层次遍历。点击阅读原文到 CSDN 阅读效果更佳。

1.先序遍历

  访问过一个节点就不会返回，所以需要一个数据结构将它的孩子节点保存起来。由于左子树的所有节点都比右子树先访问，所以当前访问的节点的左孩子的孩子节点都会比当前访问节点的右孩子先访问，而左孩子的孩子节点肯定比右孩子后保存进入数据结构，但要先被访问，满足后进先出，使用栈。具体的解法如下：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // 后进先出，所以右孩子先进栈
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

递归解法：

private List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) return result;
    result.add(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    return result;
}

力扣144.二叉树的前序遍历：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

2.中序遍历

  顺序是左-根-右，所以一直往左走，并使用一个栈保存节点，走到最左说明可以访问，于是从栈中取出并访问，访问之后再拐向右边，同样是先进先出，需要借助栈。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    Deque<TreeNode> stack = new LinkedList<>();
    if (root == null) return list;
    while (root != null || !stack.isEmpty()) {
        if (root != null) {
            stack.push(root);
            root = root.left; // 不断向左
        } else { // 为空说明走到了最左边，可以访问节点了
            root = stack.pop();
            list.add(root.val);
            root = root.right; // 转向右边继续上面的操作
        }
    }
    return list;
}

递归解法：

private List<Integer> result = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) return result;
    inorderTraversal(root.left);
    result.add(root.val);
    inorderTraversal(root.right);
    return result;
}

力扣94.二叉树的中序遍历：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

3.后序遍历

  访问的顺便是左-右-根，借助两个栈来翻转顺序。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    // stack1 用来过度
    Deque<TreeNode> stack1 = new LinkedList<TreeNode>();
    // stack2 真正存放访问的顺序
    Deque<TreeNode> stack2 = new LinkedList<TreeNode>();
    if (root == null) return list;
    stack1.push(root);
    while(!stack1.isEmpty()) {
        root = stack1.pop();
        stack2.push(root);
        if (root.left != null) {
            stack1.push(root.left);
        }
        if (root.right != null) {
            stack1.push(root.right);
        }
    }
    while(!stack2.isEmpty()) {
        list.add(stack2.pop().val);
    }
    return list;
}

递归解法：

private List<Integer> result = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) return result;
    inorderTraversal(root.left);
    inorderTraversal(root.right);
    result.add(root.val);
    return result;
}

力扣145.二叉树的后序遍历：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/