大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

怎样返回的python中序遍历

这期内容当中小编将会给大家带来有关怎样返回的python中序遍历,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。

创新互联公司是专业的都昌网站建设公司,都昌接单;提供做网站、成都做网站,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行都昌网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

【题目】

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
 

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

【思路】

前序遍历、中序遍历、后序遍历,这三种遍历方式中,前中后指的都是根节点的顺序,并且都是先遍历左子树、再遍历右子树。

中序遍历递归解法:先递归遍历左子树,再访问当前节点的值,最后递归遍历右子树。

中序遍历非递归解法:使用两个栈,一个栈(栈1)存储节点,另一个栈(栈2)存储访问标签。要想实现左根右的顺序,则需要先插入右节点,再插入根节点,最后插入左节点,实现步骤为:如果栈1的栈顶节点没被访问,则弹出该节点,并将右孩子节点(若有)加入栈中,将该节点加入栈,最后将左孩子节点(若有)加入栈中;同时栈2加入对应的是否被访问的标签。

【代码】

python版本

递归解法

# 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 traverse(self, node):
        if not node:
            return
        
        # 左根右
        self.traverse(node.left)
        self.res.append(node.val)
        self.traverse(node.right)
    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res
 

非递归解法

class Solution:    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        '''非递归遍历'''
        if not root:
            return []
        stack = [root]
        visit = [0]
        res = []
        while len(stack) > 0:
            # 已经遍历过,将val放到res中
            if visit[-1] == 1:
                res.append(stack.pop().val)
                visit.pop()
            # 未遍历过,则遍历左右节点(由于是栈,先保存右节点,再保存左节点)    
            else:
                node = stack.pop()
                visit_i = visit.pop()
                if node.right:
                    stack.append(node.right)
                    visit.append(0)
                stack.append(node)
                visit.append(1)
                if node.left:
                    stack.append(node.left)
                    visit.append(0)
                
        return res

上述就是小编为大家分享的怎样返回的python中序遍历了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。


网站栏目:怎样返回的python中序遍历
文章转载:http://dzwzjz.com/article/ghgcgs.html
在线咨询
服务热线
服务热线:028-86922220
TOP