0%

LeetCode590 | N 叉树的后序遍历

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw


每天分享一个LeetCode题目

每天 5 分钟,一起进步

LeetCode N 叉树的后序遍历,地址: https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

树结点类

1
2
3
4
class TreeNode(object):
def __init__(self, val, children=[]):
self.val = val
self.children = children

N 叉树的后序遍历

利用递归,依然遵循「左右根」的遍历原则

1
2
3
4
5
6
def postorder(self, root):
if not root:
return
for node in root.children:
self.postorder(node)
print(root.val, end=" ")

是不是看起来特别简单,但是这样不符合 LeetCode 题目中的要求

需要将结果放到一个数组中,所以需要提前初始化一个 list 进行存放

重新编码看看

1
2
3
4
5
6
7
8
9
10
11
12
def postorder_lc(self, root):
res = []

def post_order(root):
if not root:
return
for node in root.children:
post_order(node)
res.append(root.val)

post_order(root)
return res

就是提前初始化了 res,然后在遍历的时候进赋值操作

完整代码

可直接执行

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# -*- coding:utf-8 -*-
# !/usr/bin/env python

# 树结点类
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children


class Solution(object):
def postorder(self, root):
if not root:
return
for node in root.children:
self.postorder(node)
print(root.val, end=" ")

def postorder_lc(self, root):
res = []

def post_order(root):
if not root:
return
for node in root.children:
post_order(node)
res.append(root.val)

post_order(root)
return res


if __name__ == "__main__":
# 新建节点
root = Node('A')
node_B = Node('B')
node_C = Node('C')
node_D = Node('D')
node_E = Node('E')
node_F = Node('F')
node_G = Node('G')
node_H = Node('H')
node_I = Node('I')
# 构建三叉树
# A
# / | \
# B C D
# /|\ / \
# E F G H I
root.children = [node_B, node_C, node_D]
node_B.children = [node_E, node_F, node_G]
node_D.children = [node_H, node_I]

s = Solution()
s.postorder(root)
print("\n")
print(s.postorder_lc(root))

最后

在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!

------ 全文结束------