LeetCode 144. Binary Tree Preord

问题描述

给定一颗二叉树，以先序遍历的顺序返回其节点。

栗子：

输入：[1,null,2,3]

   1
    \
     2
    /
   3

输出：[1,2,3]

最后，题主还附加了一句：使用递归没啥，你能够用遍历的方式完成吗？

想看英文原文的戳这里。

解题思路

首先，介绍一下先序遍历。

始终是先遍历根节点，再遍历左节点，最后遍历右节点。对于子树也一样。

递归

使用递归的方式是最简单的，按根节点 -> 左节点 -> 右节点的顺序即可。

由于题目要求返回遍历的节点，因此将节点存入数组就好。

直接上代码：

var preorderTraversal = function (root) {
  let result = [];
  preoderTraversalRecursive(root, result);

  return result;
};

var preoderTraversalRecursive = function (root, result) {
  if (root) {
    // 根节点
    result.push(root.val);

    // 左节点
    preoderTraversalRecursive(root.left, result);
    
    // 右节点
    preoderTraversalRecursive(root.right, result);
  }
};

遍历

如果以遍历的方式，稍微复杂一丢丢，但是实现起来也不困难。

主要是利用栈的思想，先进后出。由于左节点要先于右节点遍历，因此将右节点先进栈，左节点后进栈。

该实现的 js 代码如下：

var preoderTraversalIterative = function (root) {
  let result = [];

  if (root) {
    let list = [];
    list.push(root);
    while (list.length > 0) {
      // 取第一个数据
      const node = list.shift();
      result.push(node.val);

      // 右节点进栈
      if (node.right) {
        list.unshift(node.right);
      }

      // 左节点进栈
      if (node.left) {
        list.unshift(node.left);
      }
    }
  }

  return result;
};