[LeetCode/LintCode] Binary Tree Postorder Traversa

Amio 发布于2019-08-14 15:48 / 3290人阅读

摘要：不用递归吗没问题，我们用做，速度惊人。对于左子树，放入链表对于右子树，直接移动。这样每次用将放入结果数组的首位，再将放入首位，每次再将的左子树放入链表，当右子树遍历完后，再从链表中以的顺序取出从上到下的左子树结点，以相同方法放入首位。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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