leetcode tree 个人总结

Posted on | In ,

Traversal

DFS Traversal

关于tree，最基础的就是遍历node，主要分为DFS和BFS两种思路。DFS的recursive方法是非常明了的，所以就不再赘述，主要对iterative的遍历实现再做一些要点记录。

常规迭代方法

​ 时间复杂度分析：dfs遍历会访问每一个node一次，所以时间为O(n)，n为node的数量。

  1. Preorder (leetcode 144)

    先序遍历（Root-Left-Right）的实现是最简单的，用一个stack就可以做。一个需要注意的点是先加右节点至stack，再加左节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
        def preorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            res = []
            stack = [root]
            while stack:
                node = stack.pop()
                res.append(node.val)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            return res

    空间复杂度：O(h)，h是tree的高度。可以设想两种极端情况，当树为完全二叉树时，stack最多包含h个node，当树为链表状时，stack最多包含1个node。

  2. Inorder (leetcode 94)

    中序遍历（Left-Root-Right）的理解大概就是一路向左（途经的node全部存入stack）直到None，这时从stack中pop一次得到叶结点，同时将curNode改为叶结点的右节点。

    多注意一些细节，以及最好不要用while嵌套while的实现方法（麻烦又容易踩坑）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
        def inorderTraversal(self, root: TreeNode) -> List[int]:
            res, stack = [], []
            while stack or root:
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    node = stack.pop()
                    res.append(node.val)
                    root = node.right
            return res

    这个方法非常巧妙的避免了一个在实现中序遍历时时常碰到的问题：当我们从stack中获取node时，并不知道是否已经访问过其left subtree。这个问题也是inorder比preorder要麻烦的一个小难点，因为preorder只用粗暴访问新node的左右subnode就行。为了解决这个问题，还有一些其他的方法：(1) 增加单独visited set (2)向stack中添加node时，改为(node, visited) 元组（链接）。

    inorder 也是这几种dfs遍历中最常出现在面试的。

  3. Postorder (leetcode 145)

    后序遍历（Left-Right-Root）的实现是最麻烦的，但是也有一些奇技淫巧在。比如下面代码中的方法， 几个关键点：(1)以preorder的方法为基础 (2) 添加node value至result时，更改添加顺序，末尾添加改为首位添加，这样就可以使整体逆序 (3) 为了保持left-right的输出顺序，首先添加左节点至stack，再是右节点，与preorder相反。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
        def postorderTraversal(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            stack = [root]
            res = []
            while stack:
                node = stack.pop()
                res = [node.val] + res
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            return res

补充小知识：Morris Traversal

面试的follow up如果问到既不允许使用recursive，也不能用stack的方法/或者要求空间为O(1)，（假设的确存在如此邪恶的面试官的话），可以用Morris遍历。Morris遍历妙就妙在用辅助指针来存储visited关系。这个辅助指针是拿来指示mostRight node of left subtree -> root node，当某次访问时发现该辅助指针不存在，说明根节点还没访问过，反之则说明left subtree已经惨遭遍历，转向right subtree开始新一轮。具体实现就参考这条。看图示会更容易理解一些，参考这里。

不过morris属于面试超纲题，大概知道它的存在就行，上古神技只有google会考吧，不用花太多时间。

BFS Traversal

轻松快乐 level order O(n) time O(n) space

1
2
3
4
5
6
def levelOrder(self, root):
    ans, level = [], [root]
    while root and level:
        ans.append([node.val for node in level])            
        level = [kid for n in level for kid in (n.left, n.right) if kid]
    return ans

经典题型

Path Sum

Path Sum 1 (Leetcode 112 Easy)

这题找的是 root-to-leaf path，只需要返回true or false，所以recursive方法再合适不过了。一个小细节就是需要判断是否是叶结点。时间复杂度为O(n)，因为该方法在最差情况下会访问每一个节点。

1
2
3
4
5
6
7
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:	
            return False
        if not root.left and not root.right and sum == root.val:	# 判断是否叶结点
            return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)	# 不是叶结点 继续向下

这题也可以用iterative方法来做，stack + dfs，在stack中记录 (root, curSum) pair。当然这类题用 bfs+queue也完全没问题，因为只要能遍历就行。

Path Sum 2 (Leetcode 113 Medium)

同样是root-to-leaf path，这题需要保存求出所有可能的路径。recursive方法同样适用，但是不同于返回true or false的题，我们需要建立helper函数来将path参数进行传递。具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        def helper(root, curSum, target, curPath):
            if root:
                if not root.left and not root.right:
                    if curSum + root.val == target:
                        res.append(curPath + [root.val])
                    return
                helper(root.left, curSum + root.val, target, curPath + [root.val])
                helper(root.right, curSum + root.val, target, curPath + [root.val])
        helper(root, 0, sum, [])
        return res

这题的iterative实现，stack中改为(root, curSum, curPath)。同理bfs+queue。

Path Sum 3 (Leetcode 437 Easy)

无语，这题怎么可以只是easy题呢。不同于前两题，这题的path是任意parent node to child node，只要方向保存由上至下就行（还有的题是可以九曲十八弯的）。需要一个helper函数来增加参数，记忆已走过的路径/路径和。下面的实现分两种方法，第一种方法(brute force)，helper函数内是所有已经过的node的值，每到达新的点，就反向检查以该点为结尾是否有符合条件的值。第一种方法显然有改善的空间，因为反向检查的时候其实在不停重复，所以一个改进的方法就是，用pathSum list替代path list，这个pathSum list用以记录抵达当前 node的所有可能的pathSum。

用dictionary记录preSum或许会更快一些，可以参考leetcode上一些更好的解法。我的方法2的话，search会进行n次，因为搜索每一个节点，每次memo.count最多h次，time complexity是O(nh)，space同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        # self.res = 0
        # def dfs(root, cur):
        #     if not root:
        #         return
        #     s = root.val
        #     if s == sum:
        #         self.res += 1
        #     for num in cur[::-1]:
        #         s += num
        #         if s == sum:
        #             self.res += 1
        #     dfs(root.left, cur + [root.val])
        #     dfs(root.right, cur + [root.val])
        # dfs(root, []) 
        # return self.res
    
        # improved with memorization
        if not root:
            return 0
        
        self.ans = 0

        def search(root, memo):
            
            self.ans += memo.count(sum)
            
            if root.left:
                search(root.left, [x+root.left.val for x in memo] + [root.left.val])
            
            if root.right:
                search(root.right, [x+root.right.val for x in memo] + [root.right.val])
                
        search(root, [root.val])
        return self.ans

Construct Binary Tree

这类题很别致，嗯。一个重要题干信息是no duplicate exist in the tree.

Construct Binary Tree from Preorder and Inorder Traversal (Leetcode 105 Medium)

着手点：preorder中第一个值为root->以root为点分割inorder，左sublist为left subtree，右sublist为right subtree。当我们用recursive方法解决时，如果能获得preorder的sublist，就非常方便直接了（但显然很麻烦）。这时候有一个比较巧妙的点，那就是preorder总是start with root。访问完index = 0的root之后，下一个index = 1就是leftsubtree的root（也可能left subtree为None），同理递推，那么我们并不需要获得preorder的sublist，而是一路index + 1访问就行。一种简单的具体实现如下：

1
2
3
4
5
6
7
def buildTree(self, preorder, inorder):
    if inorder:
        ind = inorder.index(preorder.pop(0))
        root = TreeNode(inorder[ind])
        root.left = self.buildTree(preorder, inorder[0:ind])
        root.right = self.buildTree(preorder, inorder[ind+1:])
        return root

为了改进time efficiency，可以添加helper函数，将当前index传入/将preorder转化为deque。时间复杂度的话是O(n*n)，这题是有O(n)解法的，Stefan Pochmann大神的方法可以但没必要，主要可以改进我们的方法里index的时间损耗，参考这条解答。

Construct Binary Tree from Inorder and Postorder Traversal (Leetcode 106 Medium)

这题和前一题一个思路，只是preorder从开头找root，postorder从结尾找root。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if inorder and postorder:
            val = postorder.pop()
            idx = inorder.index(val)
            root = TreeNode(val)
            root.right = self.buildTree(inorder[idx + 1:], postorder)
            root.left = self.buildTree(inorder[:idx], postorder)
            return root
        return None

Construct Binary Tree from Preorder and Postorder Traversal (Leetcode 889 Medium)

这题的思路就不太一样了，preorder的root在开头，postorder的root在结尾。问题在于如何寻找left subtree和right subtree的在list中的分隔点index，其实想通了也非常简单，preorder中index = 1的为left subtree的root，因为首先访问root，而同样的值，在postorder中是最后访问的。所以基本方法就是，找到pre中index = 1的值->找到post中该值的index k，所以[: k + 1]段为left subtree->获取preorder中的left subtree为 [1: 1 + index + 1]段。实现如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
        if pre and post:
            root = TreeNode(pre[0])
            if len(pre) > 1:
                idx = post.index(pre[1])
                root.left = self.constructFromPrePost(pre[1: 1 + idx + 1], post[:idx + 1])
                root.right = self.constructFromPrePost(pre[1 + idx + 1:], post[idx + 1: -1])
            return root
        return None

Construct Binary Search Tree (108 109)

懒得挂代码了。108是用sorted array构建，求中点然后recursive就行。如果想改进的话（slicing需要O(n)），就建一个helper函数，参数为start idx和end idx，这样只用更新index位置，不用实际进行slicing。

109是用sorted list。一个简单的方法就是遍历一遍sorted list把它改造为sorted array。如果要改进空间为O(1)的话，就用快慢指针。

Construct Quad Tree (427 Medium)

检查是不是leaf->是的话建一个node，不是的话递归就完事了。

Binary Search Tree

to be continue..

Else

to be continue..

解题思路

to be continue..