[LintCode/LeetCode] Binary Tree Preorder Traversal

Vixb 发布于2019-08-14 15:39 / 2480人阅读

摘要：当你被的时候，人家问，一定要说，当然可以啦所以，不用，怎么办幸好，这是一道的题目，只要逐层遍历，就可以了。所以，试一试用堆栈的做法吧记得的特点是后入先出哦

Problem

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

Example

Given:

return [1,2,4,5,3].

Challenge

Can you do it without recursion?

Note

当你被challenge的时候，人家问，Can you do it without recursion? 一定要说，当然可以啦！所以，不用recursion，怎么办？幸好，这是一道preorder的题目，只要逐层遍历，就可以了。所以，试一试用堆栈的做法吧！记得Stack的特点是后入先出哦！

Solution

Recursion

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

Stack

public class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        Stack stack = new Stack();
        if (root == null) return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
        return res;
    }
}

云服务器 GPU云服务器 binary-tree binary-search-tree Preorder Traversal

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

转载请注明本文地址：https://www.ucloud.cn/yun/65921.html

[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

摘要：递归法不说了，栈迭代的函数是利用的原理，从根节点到最底层的左子树，依次入堆栈。然后将出的结点值存入数组，并对出的结点的右子树用函数继续迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

tomorrowwu 2019-08-14 15:39 评论0 收藏0
[LintCode/LeetCode] Binary Tree Level Order Traver

Problem Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / ...

makeFoxPlay 2019-08-14 15:48 评论0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论0 收藏0
[Leetcode] Construct Binary Tree from Traversal 根据

摘要：二分法复杂度时间空间思路我们先考察先序遍历序列和中序遍历序列的特点。对于中序遍历序列，根在中间部分，从根的地方分割，前半部分是根的左子树，后半部分是根的右子树。 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, constru...

caoym 2019-08-14 12:32 评论0 收藏0