三种遍历的实现方式

144. 二叉树的前序遍历 

class Solution(object):
    def helper(self, root, res):
        if not root:
            return 
        res.append(root.val)
        self.helper(root.left, res)
        self.helper(root.right, res)

    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        self.helper(root, res)
        return res 
    
    def preorderTraversal2(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res 
        stack = [root]
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return res



145. 二叉树的后序遍历

递归就记住
迭代：结果数组加入的时候从头加，栈里面先存入头节点；每次栈中弹出最后一个元素，从头加入结果数组；如果有左右节点记得加入栈！
class Solution(object):
    def helper(self, res, root):
        if not root:
            return
        self.helper(res, root.left)
        self.helper(res, root.right)
        res.append(root.val)

    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        self.helper(res, root)
        return res

    def postorderTraversal2(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        stack = [root]
        while stack:
            cur = stack.pop()
            res.insert(0, cur.val)
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        return res

class Solution(object):
    def helper(self, res, root):
        if not root:
            return res
        self.helper(res, root.left)
        res.append(root.val)
        self.helper(res, root.right)
        
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        self.helper(res, root)
        return res
中序的迭代形式最常考
开始先把所有的左节点加入栈， 第一次遍历的时候cur的顺序是文本形式的1，2，3 

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        cur = root
        stack = []
        while cur oor stack:
            while cur:
                stack.append(cur)
                cur = cur.left 
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res 



双pre 不涉及到遍历 

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return sum == root.val
        return self.hasPathSum(root.left, sum-root.val) oor self.hasPathSum(root.right, sum-root.val)

Inorder的题目和解法

基本上全和BST 升序相关 
class Solution:
    def helper(self, res, root):
        if not root:
            return 
        self.helper(res, root.left)
        res.append(root.val)
        self.helper(res, root.right)


    def kthSmallest(self, root: TreeNode, k: int) -> int:
        res = []
        self.helper(res, root)
        return res[k - 1]

Postorder的题目和解法

子模块 子树 从底层到上层
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = float('-inf')
    
    def helper(self, root):
        if not root:
            return 0
        left = max(0, self.helper(root.left))
        right = max(0, self.helper(root.right))
        self.res = max(self.res, left+right+root.val)
        return max(left, right) + root.val

    def maxPathSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.helper(root)
        return self.res
self.res存储的是结果， helper return的是一条路径

104. 二叉树的最大深度 

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

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