树遍历

/**
 * Definition for a binary tree node.
function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}
 */

递归

前序遍历

1.
var preorderTraversal = function(root) {
    const array = []
    if(!root) return array
    const Order = (node)=>{
        if(node) {
            array.push(node.val)
            Order(node.left)
            Order(node.right)
        }
    }
    Order(root)
    return array
};
2.
var preorderTraversal = function(root) {
    const array = []
    if(!root) return array
    const Order = (node)=>{
        array.push(node.val)
        if(node.left) Order(node.left)
        if(node.right) Order(node.right)
    }
    Order(root)
    return array
};

中序遍历

var inorderTraversal = function(root) {
    const res = [];
    if(!root) return res;
    function order(node){
        if(node.left) order(node.left);
        res.push(node.val);
        if(node.right) order(node.right);
    }
    order(root);
    return res;
};

后续遍历

var inorderTraversal = function(root) {
    const res = [];
    if(!root) return res;
    function order(node){
        if(node.left) order(node.left);
        if(node.right) order(node.right);
        res.push(node.val);
    }
    order(root);
    return res;
};

非递归

前序遍历

var preorderTraversal = function(root) {
    const array = []
    if(!root) return array
    const stack = []
    stack.push(root)
    while(stack.length > 0){
        const now = stack.pop()
        array.push(now.val)
        if(now.right)
            stack.push(now.right)
        if(now.left)
            stack.push(now.left)
    }
    return array
};

中序遍历

1

var inorderTraversal = function(root) {
    const res = [];
    if(!root) return res;
    const stack = [];
    let temp = root;
    while(temp) {
        stack.push(temp);
        temp = temp.left;
    }
    while(stack.length>0){
        let current = stack.pop();
        res.push(current.val);
        if(current.right){
            let temp2 = current.right;
            while(temp2){
                stack.push(temp2);
                temp2 = temp2.left;
            }
        }
    }
    return res;
};

2

var inorderTraversal1 = function(root) {
    const res = []
    if (!root) return res
    const stack = []
    let curr = root
    while (curr || stack.length) {
        while (curr) {
            stack.push(curr)
            curr = curr.left
        }
        const node = stack.pop()
        res.push(node.val)
        curr = node.right
    }
    return res
};

后序遍历

var postorderTraversal = function(root) {
    const res = [];
    if(!root) return res;
    const stack = [];
    let temp = root;
    while(temp){
        stack.push(temp);
        temp = temp.left;
    }
    let prev;
    while(stack.length > 0){
        const top = stack[stack.length-1];
        if(!top.right){
            prev = stack.pop();
            res.push(top.val);
        }else{
            if(prev!== top.right){
                let temp2 = top.right;
                while(temp2){
                    stack.push(temp2);
                    temp2 = temp2.left;
                }
            }else{
                prev = stack.pop();
                res.push(top.val);
            }
        }
    }
    return res;
};

层次遍历

var levelOrder = function(root) {
    const result = [];
    if(!root) return result;
    const queue = [];
    queue.push(root);
    while(queue.length>0){
        const layer = [];
        const length = queue.length;
        for(let i = 0;i<length;i++){
            const current = queue.shift();
            layer.push(current.val);
            if(current.left) queue.push(current.left);
            if(current.right) queue.push(current.right);
        }
        result.push(layer);
    }
    return result;
};