[分析]
迭代实现后序遍历比迭代实现先序和中序都要稍微复杂,对其一直有恐惧心理,总觉得自己不看答案做不出来……这次竟然做出来了,很开心,练习还是有效果的~
思路1:遍历到curr节点,不管三七二十一,入栈,继续访问左节点,因为后序遍历中root最后访问。问题是栈中的节点何时出栈?答案是其左右节点均被访问之后。怎么判断其左右节点均被访问过了呢?或者换个问题,怎么判断右节点没有被访问过(一路向左,左节点必然先被访问了)?答案是如果栈顶元素有右节点且右节点没有出现在结果列表的最后。
思路2:先序遍历是root->left->right,后序遍历是left->right->root,因此修改下先序遍历实现,让其访问顺序变为root->right->left,则逆序所得结果即为后序遍历结果。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
// Method 2: modification of preorder from root->left->right to root->right->left
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> postorder = new ArrayList<Integer>();
if (root == null) return postorder;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
postorder.add(curr.val);
if (curr.left != null)
stack.push(curr.left);
curr = curr.right;
} else {
curr = stack.pop();
}
}
Collections.reverse(postorder);
return postorder;
}
// Method 1
public List<Integer> postorderTraversal1(TreeNode root) {
List<Integer> ret = new ArrayList<Integer>();
if (root == null) return ret;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode top = stack.peek();
if (top.right != null && (ret.size() == 0 || ret.get(ret.size() - 1) != top.right.val))
curr = top.right; // right child has not been visited
else // no right child or has been visited
ret.add(stack.pop().val);
}
}
return ret;
}
}
分享到:
相关推荐
python python_leetcode题解之145_Binary_Tree_Postorder_Traversal
4. leetcode-145-Binary-Tree-Postorder-Traversal.md:第145题,二叉树的后序遍历,是关于树结构和递归的问题。 5. leetCode-5-Longest-Palindromic-Substring.md:第5题,最长回文子串,考察字符串处理和动态规划...
106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
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 跳跃 Algorithm 算法题解: 包括书籍算法, 程序员算法面试指南, 还有leetcode算法题 ...construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
lru缓存leetcode LeetCode_Note leetcode 个人笔记 ...[106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted
2. **二叉树**:二叉树问题是算法面试中的常客,例如“二叉树的遍历”(Preorder, Inorder, Postorder Traversal)、“判断是否为平衡二叉树”(Balanced Binary Tree)等。JavaScript 中可以用对象来表示节点,通过...
leetcode卡 LeetCode 记录一下再LeetCode上...Postorder Traversal], Tree/stack 2017.06.20 打卡[LeetCode 107. Binary Tree Level Order Traversal II], Tree/BFS 2017.06.20 打卡[LeetCode 324. Wiggle Sort II], S
9. **Binary Tree Postorder Traversal** (二叉树的后序遍历): 后序遍历有递归和迭代两种方法。在Java中,递归方法相对简单,先遍历左子树,再遍历右子树,最后访问根节点;迭代方法通常使用栈来模拟递归过程。 10....
* [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]...
递归是解决复杂问题的有效手段,例如"Binary Tree Postorder Traversal"(二叉树后序遍历)问题,可以通过递归实现。而回溯法常用于解决组合优化问题,如"Combination Sum"(组合求和),在Java中通常结合递归来实现...
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-...
poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务
Leetcode问题用JavaScript解决使用...二叉树后置遍历( https://leetcode.com/problems/binary-tree-postorder-traversal/ ) Node.js样式标准代码应遵循Node.js样式标准( https://github.com/felixge/node-style-gu
Binary Tree Postorder Traversal (145) 要求不用递归实现后序遍历 后序是left-right-root,那么首先用修正的前序root-right-left,然后reverse一下,变成left-right-root就行了,代码如下: Factorial Trailing ...
java lru leetcode ...Tree/BinaryTree BST HashTable Disjoint Set Trie BloomFilter LRU Cache Algorithm General Coding InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi