树专题

概念

树结构的基本单位是节点。

节点之间的链接，称为分支（branch）, 也可以称为边(edge)

树结构的开端，称为根（root），或根结点。

根节点之外的节点，称为子节点（child）。

没有链接到其他子节点的节点，称为叶节点（leaf）。

/* 二叉树节点类 */
class TreeNode {
    int val;         // 节点值
    TreeNode left;   // 左子节点引用
    TreeNode right;  // 右子节点引用
    TreeNode(int x) { val = x; }
}

• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。

• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。

• 二叉树的高度（height）：从根节点到最远叶节点所经过的「边的数量」。

• 节点的深度（depth）：从根节点到该节点所经过的「边的数量」。

• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的「边的数量」。

注

“深度”和”高度“说法，如果把边的数量换成节点数量，那就是都+1。

在LeetCode中，有两道题 111.二叉树的最小深度 和 104.二叉树的最大深度 ，其中 二叉树的最大深度其实跟二叉的高度的定义是一致，不过一个是算节点的数量，一个算边的数量。

类型

满二叉树

图片来自：https://www.hello-algo.com/chapter_tree/binary_tree/#2

• 叶节点的度为 0，其余节点度为 2
• 设树的高度为 $h$，则节点数量为 $2^{h+1} -1$

完全二叉树

图片来自：https://www.hello-algo.com/chapter_tree/binary_tree/#1_1

平衡二叉树

图片来自：https://www.hello-algo.com/chapter_tree/binary_tree/#3

二叉搜索树

图片来自：https://www.hello-algo.com/chapter_tree/binary_search_tree/

1. 左子树的所有节点的值 < 根节点

2. 右子树的所有节点的值 > 根节点

3. 左子树和右子树都要满足以上两点

4. 没有键值相等的节点

遍历

二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS，层次遍历则可以使用 BFS 或者 DFS 来实现。

• DFS 都可以使用「栈」来简化操作，并且其实树本身是一种递归的数据结构，因此「递归」和「栈」对于 DFS 来说是两个关键点。
• BFS 的关键点在于如何记录每一层次是否遍历完成， 我们可以用一个标识位来表式当前层的结束。

层序遍历

层序遍历（level-order traversal）从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

BFS遍历

/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}

BFS遍历的副产物-层序遍历-迭代写法

乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。

然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

注意点：在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点，BFS 遍历改造成了层序遍历

public class Solution {
    public List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

复杂度分析

• 时间复杂度为 $O(n)$ ：所有节点被访问一次，使用 $O(n)$ 时间，其中 $n$ 为节点数量。
• 空间复杂度为 $O(n)$ ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 $(n+1)/2$ 个节点，占用 $O(n)$ 空间。

BFS遍历的副产物-层序遍历-递归写法

public List<List<Integer>> resList = new ArrayList<List<Integer>>();

 public List<List<Integer>> levelOrderTraversal(TreeNode root) {
        levelOrderTraversalHelper(root, 0);
        return result;
    }

private void levelOrderTraversalHelper(TreeNode node, int level) {
        if (node == null) return;

        if (result.size() <= level) {
            result.add(new ArrayList<>());
        }

        result.get(level).add(node.val);

        levelOrderTraversalHelper(node.left, level + 1, result);
        levelOrderTraversalHelper(node.right, level + 1, result);
    }

复杂度分析

• 时间复杂度为 $O(n)$ ：对书中的每个节点都进行递归调用函数，每一层递归的操作都是$O(1)$。
• 空间复杂度为 $O(n)$ ：需要将层次顺序遍历结果存储在一个2D 列表中，该列表可以包含多达 n 个元素。

前、中、后序遍历

沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。一直进行到已发现从源节点可达的所有节点为止。

前、中、后都属于深度优先遍历（depth-first traversal），也称深度优先搜索（depth-first search, DFS）。

前序遍历

/* 前序遍历 */
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

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

1、2、5、3、6、7

中序遍历

/* 中序遍历 */
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
}

2、5、1、6、3、7

后序遍历

/* 后序遍历 */
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.add(root.val);
}

5、2、6、7、3、1

1. “递”表示开启新方法，程序在此过程中访问下一个节点。
2. “归”表示函数返回，代表当前节点已经访问完毕。

复杂度分析：

• 时间复杂度为 $O(n)$ ：所有节点被访问一次，使用 $O(n)$ 时间。
• 空间复杂度为 $O(n)$ ：在最差情况下，即树退化为链表时，递归深度达到 $n$ ，系统占用 $O(n)$ 栈帧空间。

迭代遍历

参考垃圾回收算法中标记法：

• 使用颜色标记节点的状态，新节点为白色(WHITE)，已访问的节点为灰色(GRAY)。
• 如果遇到的节点为白色，则将其标记为灰色
  • 将其右子节点、自身、左子节点依次入栈。
• 如果遇到的节点为灰色，则将节点的值输出。

前序遍历

前序遍历的顺序是 根-左-右

思路是：

1. 先将根结点入栈
2. 出栈一个元素，将右节点和左节点依次入栈（这样出栈的时候才是中左右的顺序）
3. 重复 2 的步骤

从宏观上表现为：自顶向下依次访问左侧链，然后自底向上依次访问右侧链

从上向下我们可以直接递归访问即可，从下向上我们只需要借助栈也可以轻易做到。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        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;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

后序遍历

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

迭代遍历统一法

参考垃圾回收算法中的三色标记

那么迭代遍历，其核心思想如下：

• 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
• 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
• 如果遇到的节点为灰色，则将节点的值输出。

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

表示

完美二叉树

图片来自：https://www.hello-algo.com/chapter_tree/array_representation_of_tree/

任意二叉树

图片来自：https://www.hello-algo.com/chapter_tree/array_representation_of_tree/#732

完全二叉树中，None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾。

图片来自：https://www.hello-algo.com/chapter_tree/array_representation_of_tree/#732

AVL树

AVL 树是「平衡」二叉「搜索树」。

在需要频繁进行「增删查改」操作的场景中，AVL 树能始终保持高效的数据操作性能，时间复杂度保持在 $O(longn)$ 中

递归三要素

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

递归可视化

https://labuladong.online/algo-visualize/

let preorderResult = [];
let inorderResult = [];
let postorderResult = [];

function traverse(root) {
    if (root === null) {
        return;
    }
    // 前序遍历
    preorderResult.push(root.val);
    // 递归遍历左子树
    traverse(root.left);
    // 中序遍历
    inorderResult.push(root.val);
    // 递归遍历右子树
    traverse(root.right);
    // 后序遍历
    postorderResult.push(root.val);
}

let preorderIteratorResult = [];
let inorderIteratorResult = [];
let postorderIteratorResult = [];
function preorderTraversal(root) {
    if (root === null) {
        return preorderIteratorResult;
    }
    const stack = [root];
    while (stack.length > 0) {
        const node = stack.pop();
        preorderIteratorResult.push(node.val);
        if (node.right !== null) {
            stack.push(node.right);
        }
        if (node.left !== null) {
            stack.push(node.left);
        }
    }
    return preorderIteratorResult;
}


function inorderTraversal(root) {
    if (root === null) {
        return inorderIteratorResult;
    }
    const stack = [];
    let cur = root;
    while (cur !== null || stack.length > 0) {
        if (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            inorderIteratorResult.push(cur.val);
            cur = cur.right;
        }
    }
    return inorderIteratorResult;
}

function postorderTraversal(root) {
    if (!root) {
        return postorderIteratorResult;
    }
    const stack = [root];
    while (stack.length > 0) {
        const node = stack.pop();
        postorderIteratorResult.push(node.val);
        if (node.left) {
            stack.push(node.left);
        }
        if (node.right) {
            stack.push(node.right);
        }
    }
    return postorderIteratorResult.reverse();
}

let allRoot = TreeNode.create([1, 2, 3, null, 5, 6, 7]);
traverse(allRoot);
preorderTraversal(allRoot);
inorderTraversal(allRoot);
postorderTraversal(allRoot);

题目

层序遍历题目：

• 102.二叉树的层序遍历(opens new window)
• 107.二叉树的层次遍历II(opens new window)
• 199.二叉树的右视图(opens new window)
• 637.二叉树的层平均值(opens new window)
• 429.N叉树的层序遍历(opens new window)
• 515.在每个树行中找最大值(opens new window)
• 116.填充每个节点的下一个右侧节点指针(opens new window)
• 117.填充每个节点的下一个右侧节点指针II(opens new window)
• 104.二叉树的最大深度(opens new window)
• 111.二叉树的最小深度