数据结构 | 二叉树刷题指引（面试高频基础题）

作者: 彭旭锐 | 来源:发表于2020-09-14 03:28 被阅读0次

数据结构 | 二叉树刷题指引（面试高频基础题）
资深面试官总结：金三银四，各大厂的面试题目及答案，助你上位..
剑指offer-Python版（上）
[Leetcode]Leetcode分类刷题全记录
BD1 - Java 1-1
代码面试需要知道的8种数据结构(附面试题及答案链接)
【算法】二叉树遍历算法总结：前序中序后序遍历
LeetCode Top 100 高频算法题 07：11. Co
人生跃迁记录史
研究生学习书单

前言

优秀的算法往往取决于采用的数据结构，在算法面试中，通常涉及较多的还是基本的数据结构，其中树（Tree）是最常考的，也是最难的，建议应试者优先准备关于树的面试题；
在这篇文章里，我将梳理树的基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章

《数据结构 | 二叉树刷题指引（面试高频基础题）》

1. 概述

从逻辑上来说，树（Tree）是一种非线性结构，树的节点包含元素值与所有子节点的列表。如果按照图的理论来说，树可以看作是一种特殊的图（N 个节点和 N - 1 条边的有向无环图）；

从存储上来说，树可以采用数组 & 链表两种存储方式。链表存储法很直接明了，就是每个节点里都持有子节点的引用，而数组存储法则需要利用下标来寻找父子节点关系，节点内部不再需要持有子节点的引用，以二叉树为例：

第 [0] 位不存储，根节点存储在第 [1] 位

对于第 [i] 位上的节点，第 [2 * i] 位是其左节点，第[2 * i + 1] 位是起右节点

对于第 [i] 位上的节点，第 [i / 2] 位是其父节点

链式与数组对比（引用自《数据结构与算法之美》—— 王争著）

2. 树的遍历

树的遍历是树最最重点的知识，也是常考的点，因为在解决其他问题的时候，通常就需要遍历整棵树来寻找答案，所以我们必须对 树的各种遍历方式 非常熟悉（特别是二叉树的遍历），同时，递归与非递归 两种实现都需要掌握。

总结常见的题目，可以将遍历一棵树的方式分为：前序遍历 & 中序遍历 & 后序遍历 & 层序遍历 & 路径遍历，这几种遍历方式较常见，另外还有一种比较冷门的垂序遍历。

解决前序遍历 & 中序遍历 & 后序遍历这三类问题，需要使用 DFS 遍历，解决层序遍历问题需要使用 BFS 遍历，两个的遍历路径如下图：

DFS & BFS 对比（引用自 LeetCode）

2.1 前序遍历 & 中序遍历 & 后序遍历

这三种遍历的区别：访问到一个节点时，处理当前节点与处理左右子树的顺序不同。在前序遍历中，访问节点顺序与处理节点顺序是一致的，而另外两种是不一致的。

Preorder (root) {
  1. access content of root 
  2. Call Preorder(root.left)
  3. Call Preorder(root.right)
}

Postorder (root) {
  1. Call Postorder(root.left)
  2. Call Postorder(root.right)
  3. access content of root
}

Inorder (root) {
  1. Call Inorder(root.left) 
  2. access content of root
  3. Call Inorder(root.right)
}

递归解法
递归解法可以说很简单了，就是调整左右子树的递归顺序即可：

非递归解法
BFS 的非递归解法需要利用栈的 LIFO 特性：

复杂度：
- 时间复杂度： $O(n)$
- 空间复杂度：树退化链表时最差 $O(n)$ 、树平衡时最优 $O(lgn)$ ，平均 $O(lgn)$
本节对应题目：

2.2 层序遍历

层序遍历需要利用队列的 FIFO 特性，即：每次迭代都将一整层的节点放进队列里，如下图所示：

层序遍历（引用自《BFS 的使用场景总结：层序遍历、最短路径问题》 —— nettee 著）

fun levelOrder(root: TreeNode?): List<List<Int>> {
        val result = ArrayList<List<Int>>()

        val queue: Queue<TreeNode> = LinkedList()

        if (null != root) {
            queue.offer(root)
        }

        while (!queue.isEmpty()) {
            val level = ArrayList<Int>()
            // 处理一层
            for (index in 0 until queue.size) {
                val node = queue.poll()
                level.add(node.`val`)
                if (null != node.left) {
                    queue.offer(node.left)
                }
                if (null != node.right) {
                    queue.offer(node.right)
                }
            }
            if (level.isNotEmpty()) {
                result.add(level)
            }
        }
        return result
    }

另外，层序遍历也是常见的变型题，例如自底向上、锯齿形，其实无非就是改变输出结果的步骤：

- 锯齿形：

var flag = true

for(...){
    if(flag){
        level.add(node.`val`)
    }else{
        level.addFirst(node.`val`)
    }
}
...
flag = !flag

- 自底向上：

for(...){
    ...
}

result.addFirst(level)

复杂度：
- 时间复杂度： $O(n)$
- 空间复杂度：树退化链表时最差 $O(n)$ 、树平衡时最优 $O(lgn)$ ，平均 $O(lgn)$
本节对应题目：

2.3 路径遍历

路径遍历其实是前面四种遍历的升级版，无非就是将经过的节点记录到String。下图的 DFS 解法使用了最简单的前序遍历方法：

复杂度：
- 时间复杂度：需要复制字符串， $O(n^2)$
- 空间复杂度：树退化链表时最差 $O(n^2)$ 、树平衡时最优 $O((lgn)^2)$ ，平均 $O((lgn)^2)$
本节对应题目：
- 257. Binary Tree Paths 二叉树的所有路径【题解】

2.4 垂序遍历

Editting...

本节对应题目：
- 987. Vertical Order Traversal of a Binary Tree 二叉树的垂序遍历

3. 树的概念

通常来说不会直接考察树的相关概念，但是理解清楚这些概念是解决其他复杂问题的基础。

树的相关概念（引用自《数据结构与算法之美》—— 王争著）

路径：从一个节点走到另一个节点的经过的节点

距离：两个节点到最近共同祖先的路径和（通常指最短距离）

高度：从节点到叶子节点的路径

深度：从节点到根节点的路径

宽度：每层两个端点（该层最左和最右的非空节点，两端点间的 null 节点也计入长度）之间的长度

本节相关题目：

4. 递归思想

经常地，一棵树要满足某种性质，都会要求它的每个节点也都满足该性质，例如对于一棵二叉搜索树，从它的每棵子树观察，都是一棵二叉搜索树；或者当我们要求解一棵树的某个问题时，一般都可以先求出左右两棵子树的解，再结合当前节点求出最终解。因此，往往可以通过递归函数求解树相关的问题。例如：求二叉树的最大深度：

要求一棵树的最大深度，如果已知左右两个子树的最大深度，那么很明显这棵树的最大深度，就是两棵子树结果的最大值再加一。所以这个问题用递归就很轻松可以解决，当然是用层序遍历也能解决：

fun maxDepth(root: TreeNode?): Int {
    if (root == null) {
        return 0
    } else {
        val leftHeight = maxDepth(root.left)
        val rightHeight = maxDepth(root.right)
        return Math.max(leftHeight, rightHeight) + 1
    }
}

5. 路径问题

前面我们定义了路径的概念：从一个节点走到另一个节点的经过的节点，这一节我们专门讨论路径相关的问题。

5.1 向下的路径（从根到叶子的路径）

这一类问题找出一条满足某个条件的路径，要求路径是从根节点到叶子节点。这等于是指明了路径的起始点和终止点，因此这类问题只需要按照 第2.3节 - 路径遍历 即可轻松解决。

路径要求从根节点到叶子节点

本节相关题目：

5.2 向下的路径（非必须从根到叶子）

这一类问题找出一条满足某个条件的路径，但是不要求路径是从根节点到叶子节点，可以经过也可以不经过。因此路径的起始点和终止点就不确定了，难度会稍稍增大，那么应该怎么解呢？这就要引入 前缀和 的概念。

路径不要求从根节点到叶子节点

本节相关题目：

5.3 自由路径

让我们看看这个题目：124. Binary Tree Maximum Path Sum 二叉树的最大路径和【题解】，题目难度进一步加大，因为路径的方向不再是从上到下的单向路径，那么应该怎么解呢，还记得递归思想吗？

题目虽然不要求结果一定要经过根节点，但是如果我们假设结果是经过根节点的。给定一棵树，假设已知左子树和右子树的最大路径和，那么对于当前树，最大路径和就是两棵子树结果最大值加上根节点的值（是不是发现跟递归求树的最大深度很像呢？）

当然，根节点的最大路径和不一定是整棵树的最大路径和，因此我们需要使用一个变量记录录得的最大值。

class Solution {
    fun maxPathSum(root: TreeNode?): Int {
        var result = Integer.MIN_VALUE

        fun search(node: TreeNode?): Int {
            if (null == node) {
                return 0
            }
            // 左问题结果 
            val leftResult = Math.max(0, search(node.left))
            // 右问题结果
            val rightResult = Math.max(0, search(node.right))
            // 选择1：不选择当前节点，选择左右子树路径结果最大值
            // 选择2：选择当前节点，两个子树路径都不选
            // 选择3：选择当前节点，外加左右子树路径结果最大值
            // 选择4：选择当前节点，外加左右子树路径
            // 更新录得最大值
            result = Math.max(result, bestChoice)
            // 返回经过当前节点的最大路径和
            return node.`val` + Math.max(leftResult, rightResult)
        }

        search(root)
        return result
    }
}