104. 二叉树的最大深度

这个题我们用两种思路考虑，第一种是分解的思路，求root的最大深度，那不就是左子树和右子树的最大深度加1就行了，对于左子树来说，它的最大深度又是它的左右子树的最大深度加1,对于每个节点，考虑的问题是一样的。对于代码，如果一个节点为None，深度也就是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变量记录深度，对于一个节点，进入的时候让深度+1,离开的时候让深度-1,当遇到叶子节点的时候更新答案，最后也能得到正确的答案。

# 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函数的定义就是求一个节点的最大深度，所以返回的是左右子树的最大深度再加上本身。然后递归调用，我们可以分别求每个节点的左右子树深度。求出这个节点的直径。然后更新答案。

总的来说，前序遍历，后序遍历，中序遍历，并不只是简单的一个遍历顺序不同，而是我们获取到的信息不一样，前序遍历是在刚进入一个节点的时候进行一些操作，只能获取前一个节点带过来的信息。而后序遍历是即将离开一个节点的时候执行的操作，已经遍历过左右子树了，也就知道左右子树的信息，我们可以利用更多的信息来做一些事情。