leetcode 314 解题思路及follow up记录

Posted on | In ,

常规解法

非常简单，随便bfs或者dfs，再用hashmap记录一下index信息就行，具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        import collections
        indexDict = collections.defaultdict(list)
        level = [(root, 0)]
        while level:
            nextLevel = []
            for node, idx in level:
                indexDict[idx].append(node.val)
                if node.left:
                    nextLevel.append((node.left, idx - 1))
                if node.right:
                    nextLevel.append((node.right, idx + 1))
            level = nextLevel
        return [indexDict[k] for k in sorted(indexDict.keys())]

Follow-up: Without using Hashmap

看似复杂，其实还好。一个tip就是假如index = 4的点存在时，必然已有index = 0/1/2/3的点，所以其实我们只要用list of list来记录就行，以及分为三种情况

  • index < 0
  • index = 0
  • index > 0

分这三个list的目的应该不难理解。具体实现如下：

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
class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        leftList, rightList, centerList = [], [], []
        level = [(root, 0)]
        while level:
            nextLevel = []
            for node, idx in level:
                if idx == 0:
                    centerList.append(node.val)
                elif idx < 0:
                    if -idx > len(leftList):
                        leftList += [[]]
                    leftList[-idx - 1] += [node.val]
                else:
                    if idx > len(rightList):
                        rightList += [[]]
                    rightList[idx - 1] += [node.val]
                if node.left:
                    nextLevel.append((node.left, idx - 1))
                if node.right:
                    nextLevel.append((node.right, idx + 1))
            level = nextLevel
        return leftList[::-1] + [centerList] + rightList