小黑再一次独立解决leetcode困难，中午没运行出来，晚上在地铁上运行出来的leetcode之旅:87. 二叉树的垂序遍历

156 阅读 0 评论 103 点赞

我是靠谱客的博主害怕黑裤，这篇文章主要介绍小黑再一次独立解决leetcode困难，中午没运行出来，晚上在地铁上运行出来的leetcode之旅:87. 二叉树的垂序遍历，现在分享给大家，希望可以做个参考。

小黑代码

复制代码

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 记录结果输出
        items = {}
        def dfs(node, pos):
            if not node:
                return
            # 将结果记录
            items[pos[1]] = (items.get(pos[1], []))
            items[pos[1]].append((node.val, pos[0]))
            dfs(node.left, (pos[0] + 1, pos[1] - 1))
            dfs(node.right, (pos[0] + 1, pos[1] + 1))
        dfs(root, (0, 0))
        results = []
        # print(items)
        for col in sorted(items.keys()):
            # print(items[col])
            results.append([item[0] for item in sorted(items[col], key = lambda x:(x[1], x[0]))])
        return results

在这里插入图片描述

自定义排序

复制代码

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        nodes = []
        def dfs(node, x = 0, y = 0):
            if not node:
                return
            nodes.append((y, x, node.val))
            # 递归遍历左右子树
            dfs(node.left, x + 1, y - 1)
            dfs(node.right, x + 1, y + 1)
        dfs(root)
        # y变化则装list
        last_y = None
        arr = []
        # 顺序key排序
        for y, x, val in sorted(nodes):
            if y != last_y:
                last_y = y
                arr.append([])
            arr[-1].append(val)
        return arr