`

Leetcode - Binary Tree Postorder

 
阅读更多
[分析]
迭代实现后序遍历比迭代实现先序和中序都要稍微复杂,对其一直有恐惧心理,总觉得自己不看答案做不出来……这次竟然做出来了,很开心,练习还是有效果的~
思路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-leetcode题解之145-Binary-Tree-Postorder-Traversal

    python python_leetcode题解之145_Binary_Tree_Postorder_Traversal

    leetcode1-240题中文题解,md格式,java

    4. leetcode-145-Binary-Tree-Postorder-Traversal.md:第145题,二叉树的后序遍历,是关于树结构和递归的问题。 5. leetCode-5-Longest-Palindromic-Substring.md:第5题,最长回文子串,考察字符串处理和动态规划...

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点

    leetcode-tree

    144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...

    145.Binary Tree Postorder Traversal二叉树的后序遍历【LeetCode单题讲解系列】

    145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的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算法题,

    leetcode 跳跃 Algorithm 算法题解: 包括书籍算法, 程序员算法面试指南, 还有leetcode算法题 ...construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac

    lrucacheleetcode-LeetCode_Note:leetcode个人笔记

    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

    LeetCode-js:用 JavaScript 解决 LeetCode 问题

    2. **二叉树**:二叉树问题是算法面试中的常客,例如“二叉树的遍历”(Preorder, Inorder, Postorder Traversal)、“判断是否为平衡二叉树”(Balanced Binary Tree)等。JavaScript 中可以用对象来表示节点,通过...

    leetcode卡-LeetCode:我的LeetCode解决方案

    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

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    9. **Binary Tree Postorder Traversal** (二叉树的后序遍历): 后序遍历有递归和迭代两种方法。在Java中,递归方法相对简单,先遍历左子树,再遍历右子树,最后访问根节点;迭代方法通常使用栈来模拟递归过程。 10....

    LeetCode最全代码

    * [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]...

    LeetCode-Feb2021

    递归是解决复杂问题的有效手段,例如"Binary Tree Postorder Traversal"(二叉树后序遍历)问题,可以通过递归实现。而回溯法常用于解决组合优化问题,如"Combination Sum"(组合求和),在Java中通常结合递归来实现...

    LeetCode:LeetCode解决方案

    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-coding_exercises:编码练习

    poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务

    leetcode:LeetCode在线法官的Java解决方案

    Leetcode问题用JavaScript解决使用...二叉树后置遍历( https://leetcode.com/problems/binary-tree-postorder-traversal/ ) Node.js样式标准代码应遵循Node.js样式标准( https://github.com/felixge/node-style-gu

    LeetCodeSolution:LeetCode的部分解决方案

    Binary Tree Postorder Traversal (145) 要求不用递归实现后序遍历 后序是left-right-root,那么首先用修正的前序root-right-left,然后reverse一下,变成left-right-root就行了,代码如下: Factorial Trailing ...

    javalruleetcode-algorithm-java:leetcode刷题

    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

Global site tag (gtag.js) - Google Analytics