欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

SCL让你1分钟学会-非递归中根遍历二叉树 数据结构二叉树javapython非递归 

程序员文章站 2022-07-10 09:18:14
...

题目

题目:非递归中根遍历二叉树,树结构如下:

 

SCL让你1分钟学会-非递归中根遍历二叉树
            
    
    
        数据结构二叉树javapython非递归 

遍历结果:20 30 40 50 80 100 120

猜想

非递归先根遍历使用栈是可以的,中根也可以吧?

简化

1.这棵树太复杂了,简单一点更容易理解.于是

SCL让你1分钟学会-非递归中根遍历二叉树
            
    
    
        数据结构二叉树javapython非递归 

 

打印结果:30 50  100。

打印这样的结果,需要50进栈,30进栈,30出栈,50出栈,100进栈再出栈

落实一下代码逻辑

根节点50进栈,左孩子30进栈,左子树30没有左孩子,30弹栈

栈不为空,50弹栈

可是100如何进栈呢?应该是50弹栈的时候,检查是否右孩子,如果有右孩子,将右孩子压栈

 

弹栈时,检查是否存在右孩子,如果有右孩子,将右孩子压栈。我们可以试试给30增加一个右孩子,比如下图:

SCL让你1分钟学会-非递归中根遍历二叉树
            
    
    
        数据结构二叉树javapython非递归 

我们再试试30弹栈的同时,将40压栈是否合适?

SCL让你1分钟学会-非递归中根遍历二叉树
            
    
    
        数据结构二叉树javapython非递归 

这个方法,可以耶,上代码,Python版本

 

class Solution(object):
    """
        50
       /  \
     30   100
    / \   / \
   20 40 80 120       
    """
    def midOrderNoRecursion(self, root):
        if not root:
            return
        stack = list()
        cur_node = root
        while stack or cur_node:
            if cur_node:
                stack.append(cur_node)
            if cur_node and cur_node.left:
                cur_node = cur_node.left
            else:
                node = stack.pop()
                print(node.val)
                if node.right:
                    cur_node = node.right
                else:
                    cur_node = None

Java版本

 

public void midOrderNoRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while (!stack.isEmpty() || curNode != null) {
            if (curNode != null) {
                stack.add(curNode);
            }
            if (curNode != null && curNode.left != null) {
                curNode = curNode.left;
            } else {
                TreeNode node = stack.pop();
                System.out.println(node.val);
                if (node.right != null) {
                    curNode = node.right;
                } else {
                    curNode = null;
                }
            }
        }
    }

 

SCL让你1分钟学会-非递归中根遍历二叉树
            
    
    
        数据结构二叉树javapython非递归 

关注源代码清单,技术人的学习清单