二叉树的前序遍历

发表于 | 分类于 |
字数统计: 643 字 | 阅读时长 ≈ 3 分钟

题目描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

img

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：

img

输入：root = [1,2]
输出：[1,2]

示例 5：

img

输入：root = [1,null,2]
输出：[1,2]

方法一：迭代

前序和中序遍历的迭代写法仅仅略有不同：

  • 前序遍历需要每次向左走之前就访问根结点
  • 而中序遍历先压栈，在出栈的时候才访问
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;

    Deque<TreeNode> stack = new LinkedList<>();
    while(root != null || !stack.isEmpty()){
      while(root != null){
        res.add(root.val); //根
        stack.push(root);
        root = root.left; //左
      }
      root = stack.pop();
      root = root.right; //右
    }
    return res;
  }
}

var preorderTraversal = function(root) {
  let res = [], stack = []
  while(root || stack.length) {
    while(root) {
      res.push(root.val) //根
      stack.push(root)
      root = root.left //左
    }
    root = stack.pop()
    root = root.right //右
  }
  return res
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。
  • 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：36.7 MB, 在所有 Java 提交中击败了42.32%的用户

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    preorder(root, res);
    return res;
  }

  public void preorder (TreeNode root, List<Integer> res) {
    if(root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
  }
}

var preorderTraversal = function(root) {
    let res = []
    preorder(root, res)
    return res
};
var preorder = function(root, res) {
    if(root === null) return 
    res.push(root.val)
    preorder(root.left, res)
    preorder(root.right, res)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

  • 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：36.9 MB, 在所有 Java 提交中击败了10.28%的用户