题目

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

示例:

输入: [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 Updated: 8/2/2019, 10:05:56 PM