13.2 树的递归

# 13.2 树的递归

对于一些简单的递归题，某些 LeetCode 达人喜欢写 one-line code，即用一行代码解决问题。我们也会展示一些这样的代码，但是对于新手，笔者仍然建议您使用多行的 if-else 判断语句。

在很多时候，树递归的写法与深度优先搜索的递归写法相同，因此本书不会区分二者。

## [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

### 题目描述

求一个二叉树的最大深度。

### 输入输出样例

输入是一个二叉树，输出是一个整数，表示该树的最大深度。

```
Input:
    3
   / \
  9  20
     / \
    15  7
Output: 3
```

### 题解

利用递归，我们可以很方便地求得最大深度。

```py
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
```

## [110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)

### 题目描述

判断一个二叉树是否平衡。树平衡的定义是，对于树上的任意节点，其两侧节点的最大深度的差值不得大于 1。

### 输入输出样例

输入是一个二叉树，输出一个布尔值，表示树是否平衡。

```
Input:
      1
     / \
    2   2
   / \
  3   3
 / \
4   4 
Output: false
```

### 题解

解法类似于求树的最大深度，但有两个不同的地方：一是我们需要先处理子树的深度再进行比较，二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个-1，使得所有其长辈节点可以避免多余的判断（本题的判断比较简单，做差后取绝对值即可；但如果此处是一个开销较大的比较过程，则避免重复判断可以节省大量的计算时间）。

```py
class Solution:
    def balancedDepth(self, root:Optional[TreeNode]):
        if not root:
            return 0
        left = self.balancedDepth(root.left)
        right = self.balancedDepth(root.right)

if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1

def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.balancedDepth(root) != -1

```

## [543. Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)

### 题目描述

求一个二叉树的最长直径。直径的定义是二叉树上任意两节点之间的无向距离。

### 输入输出样例

输入是一个二叉树，输出一个整数，表示最长直径。

```
Input:
      1
     / \
    2   3
   / \
  4   5
Output: 3
```

在这个样例中，最长直径是 [4,2,1,3] 和 [5,2,1,3]。

### 题解

同样的，我们可以利用递归来处理树。解题时要注意，在我们处理某个子树时，我们更新的最长直径值和递归返回的值是不同的。这是因为待更新的最长直径值是经过该子树根节点的最长直径（即两侧长度）；而函数返回值是以该子树根节点为端点的最长直径值（即一侧长度），使用这样的返回值才可以通过递归更新父节点的最长直径值）。

```py
class Solution:
    def updateDiameter(self, node, diameter):
        if not node:
            return 0
        left = self.updateDiameter(node.left, diameter)
        right = self.updateDiameter(node.right, diameter)
        diameter[0] = max(diameter[0], left + right)
        return max(left, right) + 1

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        diameter = [0]
        self.updateDiameter(root, diameter)
        return diameter[0]
```

## [437. Path Sum III](https://leetcode.com/problems/path-sum-iii/)

### 题目描述

给定一个整数二叉树，求有多少条路径节点值的和等于给定值。

### 输入输出样例

输入一个二叉树和一个给定整数，输出一个整数，表示有多少条满足条件的路径。

```
Input: sum = 8, tree =
        10
       / \
      5  -3
     / \   \
    3   2   11
   / \   \
  3 -2    1
Output: 3
```

在这个样例中，和为 8 的路径一共有三个：[[5,3],[5,2,1],[-3,11]]。

### 题解

递归每个节点时，需要分情况考虑：（1）如果选取该节点加入路径，则之后必须继续加入连续节点，或停止加入节点（2）如果不选取该节点加入路径，则对其左右节点进行重新进行考虑。因此一个方便的方法是我们创建一个辅函数，专门用来计算连续加入节点的路径。

```py
class Solution:
    def pathSumStartWithRoot(self, root, targetSum):
        if not root:
            return 0
        return (
            int(root.val == targetSum)
            + self.pathSumStartWithRoot(root.left, targetSum - root.val)
            + self.pathSumStartWithRoot(root.right, targetSum - root.val)
        )

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root:
            return 0
        return (
            self.pathSumStartWithRoot(root, targetSum)
            + self.pathSum(root.left, targetSum)
            + self.pathSum(root.right, targetSum)
        )
```

## [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)

### 题目描述

判断一个二叉树是否对称。

### 输入输出样例

输入一个二叉树，输出一个布尔值，表示该树是否对称。

```
Input:
    1
   / \
  2   2
 / \ / \
3  4 4 3
Output: true
```

### 题解

判断一个树是否对称等价于判断左右子树是否对称。笔者一般习惯将判断两个子树是否相等或对称类型的题的解法叫做“四步法”：（1）如果两个子树都为空指针，则它们相等或对称（2）如果两个子树只有一个为空指针，则它们不相等或不对称（3）如果两个子树根节点的值不相等，则它们不相等或不对称（4）根据相等或对称要求，进行递归处理。

```py
class Solution:
    def isLeftRightSymmetric(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return (
            self.isLeftRightSymmetric(left.left, right.right) and
            self.isLeftRightSymmetric(left.right, right.left)
        )

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.isLeftRightSymmetric(root.left, root.right)
```

## [1110. Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest/)

### 题目描述

给定一个整数二叉树和一些整数，求删掉这些整数对应的节点后，剩余的子树。

### 输入输出样例

输入是一个整数二叉树和一个一维整数数组，输出一个数组，每个位置存储一个子树（的根节点）。

```
Input: to_delete = [3,5], tree =
    1
   / \
  2   3
 / \ / \
 4 5 6 7
Output: [
    1
   /
  2
 /
4  ,6 ,7]
```

### 题解

这道题最主要需要注意的细节是如果通过递归处理原树，以及需要在什么时候断开指针。同时，为了便于寻找待删除节点，可以建立一个哈希表方便查找。笔者强烈建议读者在看完题解后，自己写一遍本题，加深对于递归的理解和运用能力。

```py
class Solution:
    def moveNodesToForest(self, root, undeleted, forest):
        if not root:
            return None
        root.left = self.moveNodesToForest(root.left, undeleted, forest)
        root.right = self.moveNodesToForest(root.right, undeleted, forest)
        if root.val in undeleted:
            if root.left:
                forest.append(root.left)
            if root.right:
                forest.append(root.right)
            root = None
        return root

def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        forest = []
        undeleted = set(to_delete)
        root = self.moveNodesToForest(root, undeleted, forest)
        if root:
            forest.append(root)
        return forest
```