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

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

程序员文章站 2022-03-06 13:32:03
...

题目

题目:非递归后根遍历(后序遍历)二叉树,树结构如下:

 

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

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

猜想

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

简化

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

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

 

打印结果:30 100 50

打印这样的结果,需要50进栈,100进栈,30进栈。那就是父节点进栈,看栈顶元素是否有孩子,如果有,右孩子进栈,左孩子进栈,最后无元素可进了,再弹栈呗

 

好简单,运行一下代码,有问题。

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

第二次栈顶元素50时,再次把100和30压栈了,进入了死循环。

我们看一下,怎么把50从栈里弹出。

 

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

观察一下,如果上一个弹出的元素,是栈顶的孩子,那么栈顶元素的孩子节点就不要进栈了

 

落实一下代码逻辑

把二叉树的根节点,压栈

查看栈顶元素是否有孩子,如果有:右孩子进栈,左孩子进栈;如果没有,弹栈

 

增加一个复杂的例子

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

看一下操作

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

这种方法,成功。上代码,Python版本

 

"""
        50
       /  \
     30   100
    / \   / \
   20 40 80 120       
"""
class Solution(object):
    def postOrderNoRecursion(self, root):
        if not root:
            return
        stack = list()
        stack.append(root)
        top = TreeNode(None)
        lastPop = TreeNode(None)
        while stack:
            # 看栈顶
            top = stack[len(stack) - 1]
            # 如果栈顶有子节点,就进栈;但是刚弹出元素就是栈顶元素的子节点,就不要重复进栈了。
            if (top.left or top.right) and lastPop is not top.right and lastPop is not top.left:
                if top.right:
                    stack.append(top.right)
                if top.left:
                    stack.append(top.left)
            else:
                lastPop = stack.pop()
                print(lastPop.val)

Java 版本

 

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

 

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

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