我要招人

去企业版

首页 > 试题广场 >

实现二叉树先序，中序和后序遍历

[编程题]实现二叉树先序，中序和后序遍历

热度指数：170842 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

数据范围： $0 \le n \le 1000$ ，树上每个节点的val值满足 $0 \le val \le 100$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

样例解释：

如图二叉树结构

示例1

输入

{1,2,3}

输出

[[1,2,3],[2,1,3],[2,3,1]]

说明

如题面图

示例2

输入

{}

输出

[[],[],[]]

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

sjqg

class Solution:
    def threeOrders(self , root ):
        # write code here
        pre_order_=[];mid_order_=[];post_order_=[]
        def pre_order(root):
            if root==None:
                return None
            elif root.left==None and root.right==None:
                pre_order_.append(root.val)
            else:
                pre_order_.append(root.val)
                pre_order(root.left)
                pre_order(root.right)
        
        def mid_order(root):
            if root==None:
                return None
            elif root.left==None and root.right==None:
                mid_order_.append(root.val)
            else:
                mid_order(root.left)
                mid_order_.append(root.val)
                mid_order(root.right)
                
        def post_order(root):
            if root==None:
                return None
            elif root.left==None and root.right==None:
                post_order_.append(root.val)
            else:
                post_order(root.left)
                post_order(root.right)
                post_order_.append(root.val)

        pre_order(root)
        mid_order(root)
        post_order(root)
        return [pre_order_,mid_order_,post_order_]

发表于 2021-09-05 10:43:21 回复(0)

Python

wengJJ

Python

遇到树结构一般都可以从递归的思考方向入手

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 the root of binary tree
# @return int整型二维数组
#
class Solution:
    def mlr_dfs(self,root):
        if not root:
            return None
        self.result1.append(root.val)
        self.mlr_dfs(root.left)
        self.mlr_dfs(root.right)
    def lmr_dfs(self,root):
        if not root:
            return None
        self.lmr_dfs(root.left)
        self.result2.append(root.val)
        self.lmr_dfs(root.right)
    def rml_dfs(self,root):
        if not root:
            return None
        self.rml_dfs(root.left)
        self.rml_dfs(root.right)
        self.result3.append(root.val)
    def threeOrders(self , root ):
        # write code here
        result = []
        self.result1 = []
        self.mlr_dfs(root)
        result.append(self.result1)
        self.result2 = []
        self.lmr_dfs(root)
        result.append(self.result2)
        self.result3 = []
        self.rml_dfs(root)
        result.append(self.result3)
        return result
#     简化一下就是评论区的简化版答案
# class Solution:
#     def threeOrders(self , root ):
#         # write code here
#         self.res = [[],[],[]]
#         self.dfs(root)
#         return self.res
        
#     def dfs(self,root):
#         if not root: return
#         self.res[0].append(root.val)
#         self.dfs(root.left)
#         self.res[1].append(root.val)
#         self.dfs(root.right)
#         self.res[2].append(root.val)
#         return

发表于 2021-04-30 15:44:46 回复(2)

Python

今天就有offer啦

class Solution:
    pre, inn, post = [], [], [] #用来存储先序遍历、中序遍历、后序遍历结果
        ##先序遍历
    def preOrderRecur(self, root):
        if root==None: return []
        self.pre.append(root.val) ##根
        self.preOrderRecur(root.left) ##左
        self.preOrderRecur(root.right) ##右
    ##中序遍历
    def innOrderRecur(self, root):
        if root==None: return []
        self.innOrderRecur(root.left) #左
        self.inn.append(root.val) #根
        self.innOrderRecur(root.right) #右
    def postOrderRecur(self, root):
        if root==None: return []
        self.postOrderRecur(root.left)
        self.postOrderRecur(root.right)
        self.post.append(root.val)
    def threeOrders(self , root ):
        # write code here
        res = []
        self.pre.clear()
        self.inn.clear()
        self.post.clear() #后台有多组数据所以要清空
        if root == None: 
            return res
        self.preOrderRecur(root) #先序遍历
        self.innOrderRecur(root) #中序遍历
        self.postOrderRecur(root) #后序遍历
        res.append(self.pre) #将遍历结果放入res
        res.append(self.inn)
        res.append(self.post)
        return res

发表于 2021-04-04 16:13:49 回复(0)

Python

Rossie_Zhu

class Solution:
    def threeOrders(self , root ):
        # write code here
        self.res = [[],[],[]]
        self.dfs(root)
        return self.res
        
    def dfs(self,root):
        if not root: return
        self.res[0].append(root.val)
        self.dfs(root.left)
        self.res[1].append(root.val)
        self.dfs(root.right)
        self.res[2].append(root.val)
        return

在一个dfs里直接遍历了

发表于 2020-09-05 15:43:30 回复(11)

Python

hello__python

利用递归思想。

class Solution:
def threeOrders(self , root ):
ret=[]
pre=[]
def preorder(root):
if root is None:
return
pre.append(root.val)
preorder(root.left)
preorder(root.right)

preorder(root)
ret.append(pre)

mid=[]
def midorder(root):
if root is None:
return
midorder(root.left)
mid.append(root.val)
midorder(root.right)
midorder(root)
ret.append(mid)

last=[]
def lastorder(root):
if root is None:
return
lastorder(root.left)
lastorder(root.right)
last.append(root.val)
lastorder(root)
ret.append(last)


return ret

发表于 2020-09-04 18:22:06 回复(0)

Python

豆豆豆25

为什么用python写的迭代超时了，递归没超时。。？求解答

1.迭代

class Solution:
def threeOrders(self , root ):
# write code here
pre = []
mid = []
bac = []
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
mid.append(node.val)
node = node.right

stack = [root]
while stack:
node = stack.pop()
pre.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)

stack = [root]
while stack:
node = stack.pop()
bac.insert(0,node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return [pre,mid,bac]

2. 递归
class Solution:
def threeOrders(self , root ):
# write code here
def preorder(root):
if not root: return []
return [root.val]+preorder(root.left)+preorder(root.right)
def inorder(root):
if not root: return []
return inorder(root.left)+[root.val]+inorder(root.right)
def postorder(root):
if not root: return []
return postorder(root.left)+postorder(root.right)+[root.val]
return [preorder(root),inorder(root),postorder(root)]

发表于 2020-09-01 22:45:41 回复(0)

提交观点

问题信息

栈树哈希

难度：

6条回答 766收藏 15363浏览

通过挑战的用户

查看代码

牛客20133...

2023-03-14 14:38:13
zhancha...

2023-03-10 20:21:18
K乀

2023-03-04 16:37:51
已注销

2023-02-17 16:41:19
普信员

2023-01-07 22:03:13

实现二叉树先序，中序和后序遍历

输入

输出

说明

输入

输出

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题