打遍天下二叉树

在做一些二叉树的过程中,我发现,大多数题目是有规律可循的.所以打算总结一下二叉树这一块的打法.

ps: 文中的所有代码均可在 https://github.com/xfhy/Algorithms 中找到. 该项目有一些关于二叉树的基本学习代码和二叉树的题解等.

1. 基本概念

• 二叉树（binary tree） 是树的一种特殊形式。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。
• 满二叉树: 一个二叉树的所有非叶子节点都存在左右孩子,并且所有叶子节点都在同一层级上.
• 完全二叉树: 对一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n.如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树.
• 二叉查找树(又名: 二叉排序树,二叉搜索树): 这种二叉树的主要作用就是进行查找操作.它的中序遍历是排好序了的,即由小到大. 满足二叉查找树需要几个条件
  1. 如果左子树不为空,则左子树上所有节点的值均小于根节点的值
  2. 如果右子树不为空,则右子树上所有节点的值均大于根节点的值
  3. 左右子树也都是二叉查找树
• 从节点之间位置关系的角度来看，二叉树的遍历分为4种
  1. 前序遍历(根节点在前)
  2. 中序遍历
  3. 后序遍历
  4. 层序遍历
• 从更宏观的角度来看,二叉树的遍历归结为两大类
  1. 深度优先遍历(前序、中序、后序遍历)
  2. 广度优先遍历(层序遍历)

文中的二叉树节点定义如下:

public static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

2. 深度优先遍历

2.1 递归方式

递归的方式实现深度优先遍历代码非常简洁,往往只需要几行代码即可.用递归来实现深度优先遍历是比较自然的,仅仅只是输出的执行位置不同而已.下面我们来看哈代码:

//前序遍历
public void preOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.val);
    preOrderTraveral(node.left);
    preOrderTraveral(node.right);
}

//中序遍历
public void inOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderTraveral(node.left);
    System.out.println(node.val);
    inOrderTraveral(node.right);
}

//后序遍历
public void postOrderTraveral(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderTraveral(node.left);
    postOrderTraveral(node.right);
    System.out.println(node.val);
}

2.2 非递归方式

绝大多数可以用递归解决的问题,都可以用栈来解决.它们都有回溯的特性.

首先来看前序遍历,实现非递归方式前序遍历的思路:

1. 用一个栈来记录访问过的节点
2. 然后从根节点开始往左节点遍历,一直往下,直到左边没有左节点
3. 然后弹栈,继续访问弹出的这个元素的右节点.如果这个右节点有左子树的话,把当前节点当做根节点,继续重复2步骤
4. 直到把所有元素都遍历完成

//前序遍历 
public void preOrderTraveralWithStack(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不断往栈中压入左节点,直到左边没有左节点
        while (treeNode != null) {
            System.out.println(treeNode.val);
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //弹栈 访问右边节点
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.right;
        }
    }
}

然后我们来看中序遍历,在前序遍历的基础上,只需要稍等改动一下sout的位置即可.从根节点开始找二叉树的最左节点,找到最左节点后访问,对于每个节点来说,它都是以自己为根的子树的根节点,访问完之后就可以转到右儿子上了.

public void middleOrderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不断往栈中压入左节点,直到左边没有左节点
        while (treeNode != null) {
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //弹栈 访问右边节点
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.println(treeNode.val);
            treeNode = treeNode.right;
        }
    }
}

后续遍历就稍微复杂点,其实也只需要在先序遍历的基础上稍微改改就行了,先序是:中前后,改一下while中的左右压栈顺序就是: 中后前,得到数据之后再反转,即:前后中.就得到了最后的结果

public List<Integer> postOrderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        res.add(pop.val);
        if (pop.left != null) {
            stack.push(pop.left);
        }
        if (pop.right != null) {
            stack.push(pop.right);
        }
    }
    Collections.reverse(res);
    return res;
}

3. 广度优先遍历

即按照高度顺序一层一层的访问整棵树,高层次节点将会比低层次节点先被访问到.

下面来看一下用代码怎么实现二叉树的层序遍历,这里需要用到一个队列.将根节点入队,

/**
 * 二叉树层序遍历
 */
public void levelOrderTraversal(TreeNode root) {
    //1. 声明一个队列,将根节点入队
    //2. 然后将根节点出队,在根节点出队时将根节点的左节点和右节点都入队
    //3. 循环遍历队列,依次出队,在第2步中的左节点出队时,将自己视为根节点,然后将左右节点入队. 同理,右节点也一样
    //4. 遍历完队列时,所有节点的左右节点都遍历完了.
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

4. 案例

4.1 二叉树的最大深度

根节点的最大深度=左节点最大深度+右节点最大深度+1

这就非常适合递归,直接递归安排.

/**
 * 二叉树的最大深度
 * 思路: 比较左子树的最大深度和右子树的最大深度,
 * 左子树的最大深度同样也适用于这种思路,右子树的最大深度同样也适用于这种思路
 * 这就很适合递归,在访问到空节点时退出.
 * 最后深度需要+1,因为需要计算上根节点.
 */
public static int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

4.2 记录每一层的所有元素

有时候我们需要记录每一层上的所有元素,这时我们可以在上面二叉树层序遍历的基础上,稍稍改进一下即可: 遍历一层的时候,先记录这层的元素个数,再依次添加到记录的集合中,顺便把这些元素的左右节点入队. 继续遍历下一层.

/**
 * 二叉树层序遍历 且记录每一层的所有元素
 *
 * @param root 二叉树根节点
 */
public List<List<TreeNode>> levelOrderTraversals(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<TreeNode>> tree = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<TreeNode> levels = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            levels.add(poll);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
        tree.add(levels);
    }
    return tree;
}