SCL让你1分钟学会-非递归后根遍历二叉树

题目

题目：非递归后根遍历（后序遍历）二叉树，树结构如下：

 

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

猜想

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

简化

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

 

打印结果：30 100 50

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

 

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

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

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

 

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

 

落实一下代码逻辑

把二叉树的根节点，压栈

查看栈顶元素是否有孩子，如果有：右孩子进栈，左孩子进栈；如果没有，弹栈

 

增加一个复杂的例子

看一下操作

这种方法，成功。上代码，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);
            }
        }
    }

 

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