Python用非递归实现二叉树中序遍历代码分享-创新互联

这篇文章主要介绍“Python用非递归实现二叉树中序遍历代码分享”,在日常操作中,相信很多人在Python用非递归实现二叉树中序遍历代码分享问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Python用非递归实现二叉树中序遍历代码分享”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名注册雅安服务器托管、营销软件、网站建设、百色网站维护、网站推广。

中序遍历其实和就是先找到最左边节点,然后是其上级节点,再到上级节点的右边节点。

比如下面的中序遍历结果就是 DBEAFC

Python用非递归实现二叉树中序遍历代码分享

非递归实现逻辑,我想的这个比较笨。就是用一个队列做栈,先按照左边遍历压入栈中;当到左边叶子节点时候,读取并删除关联;推出栈回到上一级节点,如果上级节点没有右节点,则读取继续删除;如果有,则遍历右节点;为了防止右边遍历返回时候再次读取父节点;要记录下上次被推出节点,如果是右节点,则不读取父节点信息。

代码写的很难看,不去雕琢了,见笑。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        traversalList = []
        nodeList = []  
        # similar as Preorder traversal, the only change is that the value of node is recored when the node doesn't have left sub-node; new object removedNode as popped node, if a node's right sub-node is removedNode, then it should be popped both.
        if root != None:
            nodeList.append(root)
            currentNode = root
            removedNode = None
            while nodeList != []:
                if currentNode.left != None:
                    currentNode = currentNode.left
                    nodeList.append(currentNode)
                elif currentNode.right == None or currentNode.right == removedNode:
                    if currentNode.right == None:
                        traversalList.append(currentNode.val)
                    removedNode = nodeList.pop()
                    if nodeList!= []:
                        currentNode = nodeList[-1]
                        currentNode.left = None
                elif currentNode.right !=None:
                    traversalList.append(currentNode.val)
                    currentNode = currentNode.right
                    nodeList.append(currentNode)
                        
        return traversalList

到此,关于“Python用非递归实现二叉树中序遍历代码分享”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联-成都网站建设公司网站,小编会继续努力为大家带来更多实用的文章!


当前标题:Python用非递归实现二叉树中序遍历代码分享-创新互联
文章源于:http://scjbc.cn/article/ddgeps.html

其他资讯