SCL让你1分钟学会-非递归后根遍历二叉树 数据结构二叉树后根遍历javapython
程序员文章站
2022-07-10 10:41:16
...
题目
题目:非递归后根遍历(后序遍历)二叉树,树结构如下:
遍历结果: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); } } }
关注源代码清单,技术人的学习清单
上一篇: Ngrok反向代理实现外网访问内网
下一篇: drf+vue实现前后端分离