0%

LeetCode589 | N 叉树的前序遍历

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


每天分享一个LeetCode题目

每天 5 分钟,一起进步

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

树结点类

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

N 叉树的前序遍历

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

1
2
3
4
def preorder(self, root):
print(root.val, end=" ")
for node in root.children:
self.preorder(node)

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

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

重新编码看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def preorder(self, root):
# print(root.val, end=" ")
# for node in root.children:
# self.preorder(node)

res = []
def dfs(root):
if not root:
return
res.append(root.val)
for node in root.children:
dfs(node)
dfs(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
# -*- 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 preorder(self, root):
# print(root.val, end=" ")
# for node in root.children:
# self.preorder(node)

res = []
def dfs(root):
if not root:
return
res.append(root.val)
for node in root.children:
dfs(node)
dfs(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()
print(s.preorder(root))

最后

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

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