LeetCode刷题笔记（四）二叉树

四. 二叉树

Leetcode中的链表有一个ListNode类，我很好奇它是怎么实现的？还有树的TreeNode类。上述两者，我没有找到具体实现的代码，有人知道欢迎评论告知，感谢。
其实二叉树的许多问题，用递归的解法，代码可读性强又好理解。但是也存在因递归深度太大导致的内存占用量大的问题。注意以下两个知识点：

• 深度/广度优先搜索
• 前序/中序/后序/层次遍历[https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/]
  递归代码模板：

def recursion(level, param1, param2, ...):
    # recursion terminator
    if level > MAX_LEVEL:
        print_result
        return
    # process logic in current level
    process_data(level, data...)
    # drill down
    self.recursion(level+1, p1, ...)
    # reverse the current level status if needed
    reverse_state(level)

144. 二叉树的前序遍历

题目：前序遍历

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = list()
        self.preorder(root, res) # 递归解法
        return res

    def preorder(self, node: TreeNode, res: List[int]) -> None:
        if not node: 
            return
        res.append(node.val) # 当前
        self.preorder(node.left, res) # 左子树
        self.preorder(node.right, res) # 右子树

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        cur, stack, res = root, [], []
        while cur or stack: # 迭代解法
            while cur: # 根节点和左孩子入栈
                res.append(cur.val)
                stack.append(cur)
                cur = cur.left
            tmp = stack.pop() # 每次弹出一个元素，就到达右孩子
            cur = tmp.right
        
        return res

94. 二叉树的中序遍历

题目：中序遍历

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = list()
        self.inorder(root, res) # 递归解法
        return res

    def inorder(self, node: TreeNode, res: List[int]) -> None:
        if not node: 
            return
        self.inorder(node.left, res) # 左子树
        res.append(node.val)  # 当前
        self.inorder(node.right, res)  # 右子树

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        cur, stack, res = root, [], []
        while cur or stack:  # 迭代解法
            while cur: # cur 入栈, 并到达最左端的叶子节点。
                stack.append(cur)
                cur = cur.left
            tmp = stack.pop()
            res.append(tmp.val) # 出栈时再加入结果
            cur = tmp.right
        return res

145. 二叉树的后序遍历

题目：后序遍历

    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = list()
        self.postorder(root, res) # 递归解法
        return res

    def postorder(self, node: TreeNode, res: List[int]) -> None:
        if not node: 
            return
        self.postorder(node.left, res) # 左子树
        self.postorder(node.right, res)  # 右子树
        res.append(node.val)  # 当前

    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        cur, stack, res = root, [], []
        while cur or stack: 
            while cur: # 先到达最右端
                res.append(cur.val) # 
                stack.append(cur)
                cur = cur.right
            tmp = stack.pop()
            cur = tmp.left
        return res[::-1] # 反向输出

100. 相同的树

题目：相同的树

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: # p和q都是空
            return True
        elif not p or not q: # p和q有一个是空
            return False
        elif p.val != q.val: # p和q都不是空但是值不一样
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. 对称二叉树

题目： 对称二叉树

    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
        else: 
            return p.val == q.val and self.check(p.left, q.right) and self.check(p.right, q.left)

104. 二叉树的最大深度

题目： 二叉树的最大深度

    def maxDepth(self, root: TreeNode) -> int:
        if not root: 
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) # 递归解法

111. 二叉树的最小深度

题目：二叉树的最小深度

        if not root:
            return 0
        que = collections.deque([(root, 1)])
        while que:
            node, depth = que.popleft() # depth是用来记录深度的
            if not node.left and not node.right: # 只到某个节点没有左右子叶
                return depth
            if node.left:
                que.append((node.left, depth + 1))
            if node.right:
                que.append((node.right, depth + 1))
        return 0

108. 将有序数组转换为二叉搜索树

题目：将有序数组转换为二叉搜索树

    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            # 总是选择中间位置左边的数字作为根节点
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
            
        return helper(0, len(nums) - 1)

110. 平衡二叉树

题目：平衡二叉树

    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int: # 第104题最大深度
            if not root:
                return 0
            return max(height(root.left), height(root.right)) + 1

        if not root:
            return True
        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

112. 路径总和

题目：路径总和

    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
        # 考虑左右节点，sum与当前节点的值的差值作为函数输入
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

226. 翻转二叉树

题目：翻转二叉树
思考：如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root 为根节点的整棵子树的翻转。

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

235. 二叉搜索树的最近公共祖先

题目：二叉搜索树的最近公共祖先

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and root.val > q.val: # 都在root的左子树里
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and root.val < q.val: # 都在root的右子树里
            return self.lowestCommonAncestor(root.right, p, q)
        return root

257. 二叉树的所有路径

题目：二叉树的所有路径

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:  # 当前节点是叶子节点
                    paths.append(path)  # 把路径加入到答案中
                else:
                    path += '->'  # 当前节点不是叶子节点，继续递归遍历
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)

        paths = []
        construct_paths(root, '')
        return paths