二叉树的前序遍历 - 久染的小世界呀

一.树的前序遍历

方法一：非递归实现

主要思路：用一个指针cur,从根节点开始进行访问,先遍历左节点; 用一个stack栈堆记录访问过的节点,访问到叶子节点时,退栈,并且访问右节点

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

方法二：递归实现-最简单

let preorderTraversal = function(root){
    let result = []
    if(root){
        result.push(root.val)
        preorderTraversal(root.left)
        preorderTraversal(root.right)
    }
    return result;
}