144 二叉树前序遍历

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

题解

有递归和非递归的两种解法

递归解法

第一种方法就是递归，这种方法简单易懂，直接上代码：

function TreeNode(val, left, right) {
    this.val = val
    this.left = left
    this.right = right
}
var preOrderRecursive = function(root) {
    const preOrderInner = (root, result) => {
        if (!root) {
            return
        }
        result.push(root.val)
        preOrderInner(root.left, result)
        preOrderInner(root.right, result)
    }
    const result = []
    preOrderInner(root, result)
    return result
}

非递归解法

非递归解法，我们手动建立一个栈，观察前序遍历的特征，假设有一棵树。

    1
   / \
  2   3
  /\  /\
 4  5 6 7

它的前序遍历结果是 1 2 4 5 3 6 7 假设我们有一个栈，初始要压入1，然后为了能让2先出栈， 我们需要先将右子树压入栈，然后压入左子树。然后2出栈后，继续压入5（2的右子树），然后压入4（2的左子树）。这样一来，我们就知道怎么写出非递归的程序

var preOrderStack = function(root) {
    const result = []
    const stack = []
    if(!root) {
        return result
    }
    // 逻辑，先压入右子树，在压入左子树
    stack.push(root)

    while(stack.length > 0) {
        const current = stack.pop()
        result.push(current.val)
        //压入左右子树
        if (current.right) {
            stack.push(current.right)
        }
        if (current.left) {
            stack.push(current.left)
        }
    }
    return result
}