Pre-order
preorder(node) if node == null then return visit(node) preorder(node.left) preorder(node.right) |
iterativePreorder(node) parentStack = empty stack while (not parentStack.isEmpty() or node ≠ null) if (node ≠ null) visit(node) if(node.right ≠ null) parentStack.push(node.right) node = node.left else node = parentStack.pop() |
In-order
inorder(node) if node == null then return inorder(node.left) visit(node) inorder(node.right) |
iterativeInorder(node) parentStack = empty stack while (not parentStack.isEmpty() or node ≠ null) if (node ≠ null) parentStack.push(node) node = node.left else node = parentStack.pop() visit(node) node = node.right |
Post-order
postorder(node) if node == null then return postorder(node.left) postorder(node.right) visit(node) |
iterativePostorder(node) parentStack = empty stack lastnodevisited = null while (not parentStack.isEmpty() or node ≠ null) if (node ≠ null) parentStack.push(node) node = node.left else peeknode = parentStack.peek() if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) /* if right child exists AND traversing node from left child, move right */ node = peeknode.right else visit(peeknode) lastnodevisited = parentStack.pop()
|
Pre-order:
public List<Integer> preorderTraversal(TreeNode node) { List<Integer> list = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(!stack.isEmpty() || node != null) { if(node != null) { list.add(node.val); if(node.right != null) stack.push(node.right); node = node.left; } else { node = stack.pop(); } } return list; }
In-order:
private List<Integer> inorderIterative(TreeNode node) { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(!stack.isEmpty() || node != null) { if(node != null) { stack.push(node); node = node.left; } else { TreeNode p = stack.pop(); list.add(p.val); node = p.right; } } return list; }
Posr-order:
private List<Integer> postorderIterative(TreeNode node) { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode last = null; while(!stack.empty() || node != null) { if(node != null) { stack.push(node); node = node.left; } else { TreeNode p = stack.peek(); if(p.right != null && p.right != last) { node = p.right; } else { list.add(p.val); last = stack.pop(); } } } return list; }
Reference:
相关推荐
94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105....
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...
Leetcode-tree 94题 Binary Tree Inorder Traversal 对于树的问题,大多数我们都会使用递归的方法。原因是树的左子树也是树,右子树也是树,使用递归的方法最简单快捷。这道题是需要我们用Inorder的顺序输出节点。in...
lru缓存leetcode LeetCode_Note leetcode 个人笔记 问题清单 [1_two_sum.cpp] [10_regular-expression-matching.cpp] [100_same-tree.cpp] ...[107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted
binary-tree-inorder-traversal 无官方题解 104 maximum-depth-of-binary-tree 105 construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-...
102 Binary Tree Level Order Traversal.js(二叉树级订单Traversal.js) 103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和...
dna匹配 ...Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
lru cache leetcode leetcode 数据结构和算法的学习 学习数据结构和算法的好处 ...Traversal 中序/前序/后续遍历 Linked List 链表 Breadth-first/Depth-first search 广度优先/深度优先搜索 Tree 树/Binary Search T
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
leetcode 树节点 二叉树中序遍历 :evergreen_tree: 给定一棵二叉树,返回其节点值的中序遍历。 Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] 跟进:递归解决方案是微不足道的,你能迭代吗? 中序遍历: ...
2sum leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp ...invert_Binary_Tree.cpp - 对称树.cpp - BST_Or_Not.cpp - level_order_traversal.cpp - exponentiation_by_squaring.cpp - Maximum_Depth_B
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
LeetCode笔记本docsifyjsLeetCode算法Java c / c ++ javascript的基本知识简单的1. Two Sum 704. Classical Binary Search2.... Binary Tree Inorder Traversal144. Binary Tree Preorder Traversal145. Binary Tree
https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree Level Order Traversal 103 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level ...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
lru cache leetcode leetcode 记录自己刷leetcode时遇到的一些值得记下来的...binary-tree-preorder-traversal n-queens-ii populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...