摘要:今天刷后序遍历非递归实现时,因为以前看过借助一个栈和队列来实现,但始终模糊不清,不知道如何写,只好自己捋了一遍,然后查了下,发现和很多人写法有差异,故放出来,欢迎指正,如有知道用栈和队列方式实现的朋友,也请赐教。
今天刷后序遍历非递归实现时,因为以前看过借助一个栈和队列来实现,但始终模糊不清,不知道如何写,只好自己捋了一遍,然后查了下,发现和很多人写法有差异,故放出来,欢迎指正,如有知道用栈和队列方式实现的朋友,也请赐教。
public ArrayListpostorderTraversal(TreeNode root) { ArrayList result = new ArrayList<>(); if(root==null){ return result; } TreeNode node = root; Stack stack = new Stack<>(); Stack markStack = new Stack<>(); while(node!=null||!stack.isEmpty()){ while(node!=null){ stack.push(node); node = node.left; } while(!markStack.isEmpty()&&markStack.peek()==stack.peek()){ markStack.pop();; result.add(stack.pop().val); } if(!stack.isEmpty()){ node = stack.peek(); markStack.push(node); node = node.right; } } return result; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/71564.html
摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
阅读 2754·2023-04-25 22:51
阅读 1930·2021-10-11 10:58
阅读 3270·2019-08-30 10:49
阅读 1791·2019-08-29 17:09
阅读 3096·2019-08-29 10:55
阅读 790·2019-08-26 10:34
阅读 3389·2019-08-23 17:54
阅读 952·2019-08-23 16:06