二叉树的前序遍历

题目

给定一个二叉树，返回它的 前序 遍历。

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

代码

递归实现

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

非递归实现（迭代）

• 取根节点为目标节点，开始遍历
• 1.访问目标节点
• 2.左孩子入栈 -> 直至左孩子为空的节点
• 3.节点出栈，以右孩子为目标节点，再依次执行1、2、3

var preorderTraversal = function (root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    while (current) {
      result.push(current.val);
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    current = current.right;
  }
  return result;
};

---

Last update: November 5, 2023