首页 > itarticle > leetcode144. binary tree preorder traversal

leetcode144. binary tree preorder traversal

admin 11月 13, 2020 0

输出二叉树的前序遍历序列。

144. Binary Tree Preorder Traversal

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

For example:
Given binary tree [1,null,2,3],

1
2
3
4
5
 
1
 
  2
 /
3

return [1,2,3].

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

递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
 
List<Integer> list = new ArrayList<>();
public List<Integer> (TreeNode root) {
    if (root == null) return new ArrayList<>();
    preorderWalk(root);
    return list;
}
public void preorderWalk(TreeNode root) {
    if (root == null) return;
    list.add(root.val);
    preorderWalk(root.left);
    preorderWalk(root.right);
}

迭代算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
public List<Integer> (TreeNode root) {
    List<Integer> list = new ArrayList<>();
    ArrayDeque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while (p != null || !stack.isEmpty()) {
        while (p != null) {
            list.add(p.val);
            stack.push(p);
            p = p.left;
        }
        if (!stack.isEmpty()) {
            p = stack.pop();
            p = p.right;
        }
    }
    return list;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能