[LeetCode/LintCode] Binary Tree Postorder Traversa

Amio 發布于2019-08-14 15:48 / 3297人閱讀

摘要：不用遞歸嗎沒問題，我們用做，速度驚人。對于左子樹，放入鏈表對于右子樹，直接移動。這樣每次用將放入結果數組的首位，再將放入首位，每次再將的左子樹放入鏈表，當右子樹遍歷完后，再從鏈表中以的順序取出從上到下的左子樹結點，以相同方法放入首位。

Problem

Given a binary tree, return the postorder traversal of its nodes" values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

不用遞歸嗎？沒問題，我們用LinkedList做，速度驚人。對于左子樹，放入鏈表；對于右子樹，直接移動node：node = node.right。這樣每次用addFirst()將node放入結果數組的首位，再將root.right放入首位，每次再將root.right的左子樹放入鏈表，當右子樹遍歷完后，再從鏈表中以FIFO的順序取出從上到下的左子樹結點，以相同方法放入首位。

Solution Using LinkedList

public class Solution {
    public List postorderTraversal(TreeNode node) {
        LinkedList result = new LinkedList();
        Stack leftChildren = new Stack();
        while(node != null) {
            result.addFirst(node.val);
            if (node.left != null) leftChildren.push(node.left);
            node = node.right;
            if (node == null && !leftChildren.isEmpty()) node = leftChildren.pop();
        }
        return result;
    }
}

Using Recursion

public class Solution {
    public List postorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        if (root == null) return res;
        helper(root, res);
        return res;
    }
    public void helper(TreeNode root, ArrayList res) {
        if (root.left != null) helper(root.left, res);
        if (root.right != null) helper(root.right, res);
        res.add(root.val);
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Postorder Binary

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66024.html

145.Binary Tree Postorder Traversal

摘要：題目解答最主要的思想是先存的話，整個存儲的順序會變反，所以要插入存儲進去。題目：Given a binary tree, return the postorder traversal of its nodes values. For example:Given binary tree {1,#,2,3}, 1 2 / 3return [3,2,1]. 解答：最主要的思想是先存...

geekidentity 2019-08-14 14:14 評論0 收藏0
leetcode-145-Binary Tree Postorder Traversal

摘要：棧的意義價值具有時間性，先進后出。比如遞歸的后序遍歷，先序遍歷，二叉樹的按層次打印。根據需求不同，在中暫時儲存的元素單元也不同，元素的先后順序也不同。應用對順序有要求的數據。 stack 棧的意義價值：具有時間性，先進后出。所以具有時間關聯順序的元素可以通過這個時間。比如遞歸的后序遍歷，先序遍歷，二叉樹的按層次打印。根據需求不同，在stack中暫時儲存的元素...

Pandaaa 2019-07-30 17:30 評論0 收藏0
leetcode-106-根據中序和后序遍歷，構造二叉樹

摘要：題目描述以為中心進行分類題目分析根據中序和后序遍歷，構造二叉樹。根據動態規劃方法，找出循環的共性。構造子二叉樹，需要節點，和左右連接，從后序遍歷找出根節點，從對目標序列進行切分，如此往復。題目描述： Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may a...

widuu 2019-07-30 16:04 評論0 收藏0
[LeetCode] 590. N-ary Tree Postorder Traversal (vs

摘要：按順序放入，正好方面是從到，順序方面是從最右到最左，因為是先入后出。這樣最后一下就是先左后右，先子后根。 590. N-ary Tree Postorder Traversal Problem Given an n-ary tree, return the postorder traversal of its nodes values.For example, given a 3-ar...

sydMobile 2019-08-19 11:18 評論0 收藏0
Construct Binary Tree from Traversal

摘要：思路在的順序里，先，然后再左右。所以根據可以知道的。接著再分別在和的里面重復找以及左右的過程。首先的包括和，以及對應的起始和結束位置，對應的起始和結束位置。返回值為，因為每個里要一個，同時找到它的和，左右節點通過返回值獲得。同時的不需要了。 From Preorder and Inorder 思路在preorder的順序里，先root，然后再左右。所以根據preorder可以知道roo...

wenshi11019 2019-08-14 17:11 評論0 收藏0