[数据结构与算法]二叉树的几道相似简单递归题

二叉树中递归的思想，在这本Leetbook中讲的很细了，这里不展开。下面是几道例题：

100. 相同的树

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if (not p) and (not q):
            return True
        elif (not p) or (not q):
            return False
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

判断两个二叉树是否相同，思路如下：两个二叉树是否同时为空？是否一个为空而另一个不为空？他们的根节点值是否相同？最后是递归的判断，他们的左右子树是否都相同？

101. 对称二叉树

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.check(root, root)

    def check(self, p: TreeNode, q: TreeNode) -> bool:
        if (not p) and (not q):
            return True
        elif (not p) or (not q):
            return False
        elif p.val != q.val:
            return False
        else:
            return self.check(p.left, q.right) and self.check(p.right, q.left)

判断一个二叉树是否为对称二叉树，可以转化为判断这个树和自己的镜像树是否相同。关键在于用 self.check(root, root) 构造出两个树，然后以相反方向进行递归和判断。

104. 二叉树的最大深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return max(left_depth, right_depth) + 1

自底向上的递归，在Leetbook中有详细介绍，简单来说：如果我们知道一个根节点，以其左子节点为根的最大深度为 left_depth 和以其右子节点为根的最大深度为 right_depth ，我们就可以选择它们之间的最大值，再加上1来获得根节点所在的子树的最大深度。

543. 二叉树的直径

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 1
        
        def depth(node: TreeNode):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            # 此节点作为根节点的最大深度是否为众节点中最大，是则更新ans
            self.ans = max(self.ans, left_depth + right_depth + 1)
            return max(left_depth, right_depth) + 1

        depth(root)
        return self.ans - 1

虽然题目说明了直径（最大的两节点间路径）不一定经过根节点，但是归根到底，两节点间路径必然会有个根节点，目标就是找到把树中所有节点都作为根节点时，各自求出最大深度（上一题思路），然后在这些最大深度中找到最大的作为直径 ans。

563. 二叉树的坡度

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.ans = 0

        def val_sum(node: TreeNode):
            if not node:
                return 0
            left_sum = val_sum(node.left)
            right_sum = val_sum(node.right)
            tilt = abs(left_sum - right_sum)
            self.ans += tilt
            return left_sum + right_sum + node.val
        
        val_sum(root)
        return self.ans

本题与最大深度类似，区别在于是记录深度之差的绝对值（坡度），然后递归返回左右子树和自身值之和。

112. 路径总和

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root: # 非节点
            return False
        if not root.left and not root.right:  # 叶子节点
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

思路是如果子树的和等于 targetSum 减去当前节点的值，则存在路径。所以终止条件为非节点则返回 False，为叶子节点则返回 targetSum == 当前节点的值，函数调用是子节点和减去当前节点值后的 targetSum 。

226. 翻转二叉树

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left
        return root

递归的思想，从根节点开始，其左子树变为翻转了的右子树，其右子树变为翻转了的左子树，一直到叶节点，就是简单的左右节点交换。