二叉树遍历

// 递归版 中序
function inOrder(root) {
    if(root === null) return;
    inOrder(root.left);
    console.log(root.data);
    inOrder(root.right);
}

// 非递归版 中序
function inOrder(root) {
    // 运用一个堆栈stack
    let stack = [];
    let result = [];

    while(stack.length > 0 || root !== null) {
        if(root!== null) {
            stack.push(root);
            root = root.left;
        } else {
            let node = stack.pop();
            result.push(node.data);
            if(node.right !== null) {
                root = node.right;
            }
        }
    }
    return result;
}

// 递归版 前序
function preOrder(root) {
    if(root === null) return;
    console.log(root.data);

    preOrder(root.left);
    preOrder(root.right);
}

// 非递归版 前序
function preOrder(root) {
    let stack = [];
    let result = [];

    while(stack.length > 0 || root !== null) {
        if(root !== null) {
            stack.push(root);
            result.push(root.data);
            root = root.left;
        } else {
            let node = stack.pop();
            if(node.right !== null) {
                root = node.right;
            }
        }
    }
    return result;
}

function preOrder(root) {
    let stack = [];
    let result = [];
    if(!(root)) return [];
    stack.push(root);
    while(stack.length > 0) {
        let node = stack.pop();
        result.push(node.val);
        // 堆栈的特点：先进后出，所以我们先把右孩子放进去stack。
        if(node.right !== null) {
            stack.push(node.right);
        }
        if(node.left !== null) {
            stack.push(node.left);
        }
    }
    return result;
}

// 递归版 后序
function pastOrder(root) {
    if(root === null) return;
    pastOrder(root.left);
    pastOrder(root.right);
    console.log(root.data)
}

// 非递归 后序
var postOrder = function(root) {
    // 运用两个堆栈
    let result = [];
    let stack1 = [];
    let stack2 = [];

    if(!(root)) return [];

    stack1.push(root);

    while(stack1.length > 0) {
        let node = stack1.pop();
        stack2.push(node);
        if(node.left !== null) {
            stack1.push(node.left)
        }
        if(node.right !== null) {
            stack1.push(node.right)
        }
    }
    while(stack2.length > 0) {
        result.push(stack2.pop().val);
    }

    return result;
};


//  层次遍历
var levelOrder = function(root) {
    let hash = {};
    let result = [];
    let queue = [];
    if(!(root)) return [];

    // 用queue队列来装「元素」，这个「元素」是个数组，由两部分组成
    // 第一部分是「level层级」，第二部分是原本的「Node」
    queue.push([0, root]);

    while(queue.length > 0) {
        let current = queue.shift();
        let level = current[0];
        let node = current[1];
        //  hash 初始化
        
        if(hash[level] === undefined) {
            hash[level] = [];
        }

        hash[level].push(node.data);


        if(node.left !== null) {
            queue.push([level + 1, node.left])
        }

        if(node.right !== null) {
            queue.push([level + 1, node.right])
        }

    }
    for(let key in hash) {
        result.push(hash[key]);
    }
    return result;

};