二叉树的前序遍历-中等

难度：中等

题目描述：
给定一个二叉树，返回它的前*序 *遍历。

示例：

输入: [1, null, 2, 3];
1;
\;
2 / 3;

输出: [1, 2, 3];

1
2
3
4
5
6

解题思路：
递归法:

var inorderTraversal = function (root) {
  let result = [];
  const pushRoot = (root) => {
    if (root !== null) {
      result.push(root.val);
      if (root.left !== null) {
        pushRoot(root.left);
      }
      if (root.right !== null) {
        pushRoot(root.right);
      }
    }
  };
  pushRoot(root);
  return result;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

迭代法：

const preorderTraversal = (root) => {
  const list = [];
  const stack = [];

  // 当根节点不为空的时候，将根节点入栈
  if (root) stack.push(root);
  while (stack.length > 0) {
    const curNode = stack.pop();
    // 第一步的时候，先访问的是根节点
    list.push(curNode.val);

    // 我们先打印左子树，然后右子树
    // 所以先加入栈的是右子树，然后左子树
    if (curNode.right !== null) {
      stack.push(curNode.right);
    }
    if (curNode.left !== null) {
      stack.push(curNode.left);
    }
  }
  return list;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

← 二叉树的中序遍历-中等对称二叉树-简单 →

# 二叉树的前序遍历-中等

二叉树的前序遍历-中等