144. Binary Tree Preorder Traversal

Half 发布于2019-08-14 14:14 / 362人阅读

摘要：题目解答这里有三种方法，三种方法是三种思考问题的思路，都掌握才好。的解法的解法的解法

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

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

2
/

3
return [1,2,3].

解答：
这里有三种方法，三种方法是三种思考问题的思路，都掌握才好。
1.Iterative的解法:

public List preorderTraversal(TreeNode root) {
    List result = new ArrayList();
    Stack stack = new Stack();
    if (root == null) return result;
    
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        result.add(node.val);
    }
    return result;
}

2.Recursive的解法：

public void Traverse(TreeNode root, List result) {
    if (root == null) return;
    
    result.add(root.val);
    Traverse(root.left, result);
    Traverse(root.right, result);
}

public List preorderTraversal(TreeNode root) {
    List result = new ArrayList();
    Traverse(root, result);
    return result;
}

3.Divide & Conquer的解法

public List preorderTraversal(TreeNode root) {
    List result = new ArrayList();
    if (root == null) return result;
    
    List left = preorderTraversal(root.left);
    List right = preorderTraversal(root.right);
    
    result.add(root.val);
    result.addAll(left);
    result.addAll(right);
    
    return result;
}

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

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

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

[LeetCode] 589. N-ary Tree Preorder Traversal (vs.

589. N-ary Tree Preorder Traversal Given an n-ary tree, return the preorder traversal of its nodes values.For example, given a 3-ary tree:showImg(https://segmentfault.com/img/bVbhKkv?w=781&h=502);Retu...

array_huang 2019-08-19 11:18 评论0 收藏0
二叉树遍历算法收集(先序 preorder，后序 postorder，中序 inorder）循环+

摘要：指的是的位置。算法比较简单，算法比较难想，可是原题都说了 preorder: root-left-rightinorder: left-root-rightpostorder: left-right-root order指的是root的位置。 recursive算法比较简单，iterative算法比较难想，可是leetcode原题都说了： recursive method is tri...

沈建明 2019-08-14 15:55 评论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
[LintCode/LeetCode] Binary Tree Preorder Traversal

摘要：当你被的时候，人家问，一定要说，当然可以啦所以，不用，怎么办幸好，这是一道的题目，只要逐层遍历，就可以了。所以，试一试用堆栈的做法吧记得的特点是后入先出哦 Problem Given a binary tree, return the preorder traversal of its nodes values. Example Given: 1 / 2 3 ...

Vixb 2019-08-14 15:39 评论0 收藏0
Construct Binary Tree from Traversal

摘要：思路在的顺序里，先，然后再左右。所以根据可以知道的。接着再分别在和的里面重复找以及左右的过程。首先的包括和，以及对应的起始和结束位置，对应的起始和结束位置。返回值为，因为每个里要一个，同时找到它的和，左右节点通过返回值获得。同时的不需要了。 From Preorder and Inorder 思路在preorder的顺序里，先root，然后再左右。所以根据preorder可以知道roo...

wenshi11019 2019-08-14 17:11 评论0 收藏0