[LeetCode] 系统刷题4_Binary Tree & Divide and Conquer

The most important : [LeetCode] questions conclustion_BFS, DFS

参考[LeetCode] questions conlusion_InOrder, PreOrder, PostOrder traversal 可以对binary tree进行遍历。

此处说明Divide and Conquer 的做法，其实跟recursive的做法很像，但是将结果存进array并且输出，最后conquer (这一步worst T：O(n)) 起来，所以时间复杂度可以从遍历O(n) -> O(n^2).

实际上代码是一样, 就是把[root.val] 放在先, 中, 后就是pre, in, post order了.

1) Preorder traversal

class Solution:

    def preOrder(self, root):

        if not root: return []

        left = self.preOrder(root.left)

        right = self.preOrder(root.right)

        return [root.val] + left + right  # worst T: O(n)

Inorder traversal

class Solution:

    def inOrder(self, root):

        if not root: return []

        left = self.preOrder(root.left)

        right = self.preOrder(root.right)

        return  left + [root.val] + right  # worst T: O(n)

3) Postorder traversal

class Solution:

    def postOrder(self, root):

        if not root: return []

        left = self.preOrder(root.left)

        right = self.preOrder(root.right)

        return  left + right + [root.val] # worst T: O(n)

[LeetCode] 104. Maximum Depth of Binary Tree_Easy tag: DFS

[LeetCode] 110. Balanced Binary Tree_Easy tag: DFS

[LeetCode] 236. Lowest Common Ancestor of a Binary Tree_ Medium tag: DFS, Divide and conquer

[LeetCode] 257. Binary Tree Paths_ Easy tag: DFS

[LeetCode] 129. Sum Root to Leaf Numbers_Medium tag: DFS

[LeetCode] 112. Path Sum_Easy tag: DFS

[LeetCode] 113. Path Sum II

[LeetCode] 437. Path Sum III_ Easy tag: DFS

[LeetCode] 124. Binary Tree Maximum Path Sum_ Hard tag: DFS recursive, Divide and conquer

[LeetCode] 687. Longest Univalue Path_Easy tag: DFS recursive

[LeetCode] 298. Binary Tree Longest Consecutive Sequence_Medium tag: DFS recursive

[LeetCode] 549. Binary Tree Longest Consecutive Sequence II_ Medium tag: DFS recursive