剑指offer 面试题55 - I. 二叉树的深度（易）& LeetCode 110. 平衡二叉树（易）

这两道题的解法实际上只是树的遍历算法的应用。剑指offer 面试题55 - I是深度优先遍历一棵树，剑指offer 面试题55 - II 是广度优先遍历一棵树。

Question

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：给定二叉树 [3,9,20,null,null,15,7]， 

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
返回它的最大深度 3 。

提示：节点总数 <= 10000

测试用例

功能测试（输入普通的二叉树；二叉树中所有节点都没有左/右子树）。 特殊输入测试（二叉树只有一个节点；二叉树的头节点为nullptr指针）。

本题考点

考查应聘者对二叉树的理解及编程能力。这两道题的解法实际上只是树的遍历算法的应用。 考查应聘者对新概念的学习能力。面试官提出一个新的概念即树的深度，这就要求我们在较短的时间内理解这个概念并解决相关的问题。这是一种常见的面试题型。能在较短时间内掌握、理解新概念的能力就是一种学习能力。 考查应聘者的知识迁移能力。如果面试官先问如何求二叉树的深度，再问如何判断一棵二叉树是不是平衡的，那么应聘者应该从求二叉树深度的分析过程中得到启发，找到判断平衡二叉树的突破口。

Intuition

深度优先遍历

对树进行深度优先遍历，每次保存最大深度。

左右子树遍历

如果一棵树只有一个节点，那么它的深度为1。 如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1； 同样，如果根节点只有右子树而没有左子树那么树的深度应该是其右子树的深度加1。 如果既有右子树又有左子树，那么该树的深度就是其左、右子树深度的较大值再加1。

Code

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        self._max = 0
        def _dfs(depth, node):
            if node.left == None and node.right == None and depth > self._max:
                self._max = depth
                return
            if node.left:
                _dfs(depth + 1, node.left)
            if node.right:
                _dfs(depth + 1, node.right)
    
        _dfs(1, root)   # 从root开始，已经有一层了。
        return self._max

左右子树遍历

1
2
3
4
5
6
7
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return left + 1 if left > right else right + 1

Extention

Question

面试题55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1：给定二叉树 [3,9,20,null,null,15,7] 

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
返回 true 。

示例 2：给定二叉树 [1,2,2,3,3,null,null,4,4] 

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4
返回 false 。

限制：1 <= 树的结点个数 <= 10000

测试用例

功能测试（平衡的二叉树；不是平衡的二叉树；二叉树中所有节点都没有左/右子树）。 特殊输入测试（二叉树中只有一个节点；二叉树的头节点为 nullptr 指针）。

Intuition

简单思路

在遍历树的每个节点的时候，调用函数TreeDepth得到它的左、右子树的深度。如果每个节点的左、右子树的深度相差都不超过1，那么按照定义它就是一棵平衡二叉树。面试官不会喜欢这种思路，因为，在自顶向下遍历的过程中，每个节点会被重复计算。

每个节点只遍历一次的思路

如果我们用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之前我们就已经遍历了它的左、右子树。只要在遍历每个节点的时候记录它的深度（某一节点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个节点是不是平衡的。

后序遍历 + 剪枝 （从底至顶）

思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。此方法为本题的最优解法，但剪枝的方法不易第一时间想到。

算法流程

recur(root) 函数：

  • 返回值：
    • 当节点root 左 / 右子树的深度差 ≤1 ：则返回当前子树的深度，即节点 root 的左 / 右子树的深度最大值 +1 （ max(left, right) + 1 ）；
    • 当节点root 左 / 右子树的深度差 > 2 ：则返回 -1−1 ，代表此子树不是平衡树 。
  • 终止条件：
    • 当 root 为空：说明越过叶节点，因此返回高度 0；
    • 当左（右）子树深度为 -1 ：代表此树的 左（右）子树不是平衡树，因此剪枝，直接返回 -1；

isBalanced(root) 函数：

  • 返回值： 若 recur(root) != -1 ，则说明此树平衡，返回 true；
  • 否则返回 falsefalse 。

参考连接

作者：Krahets 链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

  • 简单思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def __init__(self):
        self.flag = True

    def isBalanced(self, root: TreeNode) -> bool:
        self.getDepth(root)
        return self.flag
    
    def getDepth(self, root):
        if root == None:
            return 0
        left = 1 + self.getDepth(root.left)
        right = 1 + self.getDepth(root.right)

        if abs(left - right) > 1:
            self.flag = False
        
        return left if left > right else right
  • 每个节点只遍历一次
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def getDepth(self, root):
        if root == None:
            return 0
        return max(self.getDepth(root.left), self.getDepth(root.right)) + 1
    
    def isBalanced(self, root: TreeNode) -> bool:
        if root == None:
            return True
        if abs(self.getDepth(root.left) - self.getDepth(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
  • 后序遍历 + 剪枝 （从底至顶）Krahets大佬版本（推荐）
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def recur(root):
            if not root: return 0
            left = recur(root.left)
            if left == -1: return -1
            right = recur(root.right)
            if right == -1: return -1
            return max(left, right) + 1 if abs(left - right) <= 1 else -1

        return recur(root) != -1