144.二叉树的 前序 遍历

[shengxinjing]

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

 示例:

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

输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

[kaizige10]

// 思路2：迭代
var preorderTraversal = function(root) {
    if (!root) return []
    let stack = [root], result = []
    while(stack.length > 0) {
        let cur = stack.pop()
        result.push(cur.val)
        cur.right && stack.push(cur.right)
        cur.left && stack.push(cur.left)
    }
    return result
}
// 思路1：递归
var preorderTraversal1 = function(root) {
    if (!root) return []

    let result = []
    result.push(root.val)
    root.left && result.push(...preorderTraversal(root.left))
    root.right && result.push(...preorderTraversal(root.right))

    return result
};

[adamma1024]

var preorderTraversal = function(root) {
    const stack = []
    const res = []
    while(root){
      // 优化点， 没有右节点无需入栈，节约空间
      if(root.right) stack.push(root)
      res.push(root.val)
      if(root.left){
        root = root.left
      }else{
        let last = stack.pop()
        root = last ? last.right : false
      }
    }
    return res
};

runtime 66.4% space 96.16%