leetcode二叉树基础练习题

104. 二叉树的最大深度

先用分解子问题的思路：一棵树的最大深度，等于左右子树最大深度中的较大值再加一。对每棵子树都应用同样的定义即可。空节点的深度为 0，这也是递归的终止条件。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        leftmax = self.maxDepth(root.left)
        rightmax = self.maxDepth(root.right)
        return 1 + max(leftmax, rightmax)

另一种写法是遍历整棵树，用 depth 记录当前深度：进入非空节点时加一，离开时减一。下面的实现走到空节点时更新答案，此时 depth 记录了走到这个位置之前的路径深度，遍历结束后即可得到最大值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.depth = 0
        self.res = 0

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        self.traverse(root)
        return self.res

    def traverse(self, root):
        if root is None:
            self.res = max(self.res, self.depth)
            return
        self.depth += 1
        self.traverse(root.left)
        self.traverse(root.right)
        self.depth -= 1

144. 二叉树的前序遍历

按“根、左、右”的顺序遍历即可。在进入节点时记录当前值，再递归访问左右子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = []

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        self.traverse(root)
        return self.res

    def traverse(self, root):
        if root is None:
            return
        self.res.append(root.val)
        self.traverse(root.left)
        self.traverse(root.right)

543. 二叉树的直径

经过某个节点的最长路径，其边数等于左子树最大深度与右子树最大深度之和。可以在后序位置取得左右子树的深度，再用两者之和更新答案。整棵树的最长路径不一定经过根节点，因此每个节点都要检查。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.maxdiameter = 0

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.maxDpeth(root)
        return self.maxdiameter

    def maxDpeth(self, root):
        if root is None:
            return 0
        leftMax = self.maxDpeth(root.left)
        rightMax = self.maxDpeth(root.right)
        mydiameter = leftMax + rightMax
        self.maxdiameter = max(self.maxdiameter, mydiameter)
        return 1 + max(leftMax, rightMax)

代码中的 maxDpeth 返回当前节点的最大深度，也就是左右子树深度的较大值加一。同时，它用左右深度之和计算经过当前节点的最长路径，并更新 maxdiameter。返回值和更新答案这两件事需要区分开。

从这几道题可以看到，前序、中序、后序不只是访问顺序不同，执行操作时能利用的信息也不同。前序位置刚进入节点，可以使用父节点传下来的状态；后序位置已经处理完左右子树，可以利用子树返回的结果。像直径这样的题，就适合在后序位置汇总信息。