顺序遍历二叉树

先序遍历

  • 访问根节点
  • 访问左子树
  • 访问右子树

递归以上过程

中序遍历

按照“左中右”的顺序访问

简单代码

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

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

后序遍历

按照“左右中”的顺序遍历

三种方法比较

层次遍历二叉树

使用队列实现

每个根节点出队时，将他的孩子入队

线索二叉树

利用二叉树的空指针域：

  • 如果某节点左为空，则指向前驱
  • 如果某节点右为空，则指向后继

标志域说明有没有对应子节点