二叉树的遍历

[AILINGANGEL]

先序遍历

• 递归(easy)

var preorderTraversal = function(root) {
    let ans = [];
    helper(root, ans);
    return ans;
};
var helper = function(root, arr) {
    if (root) {
        arr.push(root.val); //先把根节点的值加入到结果集中
        helper(root.left, arr);//把左孩子的值加入到结果集中
        helper(root.right, arr);//把右边孩子的值加入到结果集中
    }
};

• 迭代
  核心思想: 从根节点开始，如果根节点不为空，就将节点压栈，并且将节点的值放到最后的结果中；再一次遍历左孩子，直到左孩子为null；这个时候让栈顶的元素出栈，并访问栈顶元素的右孩子，对右孩子又执行刚刚遍历左孩子的操作，依次迭代下去。

let node = root;
    let stack = [];
    let ans = [];
    while (node !== null || stack.length > 0) {
        if (node) {
            ans.push(node.val); // 在left child之前加入结果集
            stack.push(node);
            node = node.left;
            continue;
        }
        node = stack.pop();
        node = node.right;
    }
    return ans;

中序遍历

• 递归(easy)

var inorderTraversal = function(root, arr) {
    if (root) {
        inorderTraversal(root.left, arr);
        arr.push(root.val);
        inorderTraversal(root.right, arr);
    }
};

• 迭代
  核心思想: 从根节点开始，如果节点不为空就压栈，直到找到二叉树的最左边的孩子。然后开始让节点出栈，并保存节点的值，因为中序遍历先遍历左孩子再遍历根节点，这样可以保证左孩子在根节点的前面。然后再遍历出栈元素的右孩子，对右孩子又开始遍历左孩子的操作。

var inorderTraversal = function(root, arr) {
    let node = root;
    let ans = [];
    let stack = [];
    while (node !== null || stack.length > 0) {
        if (node) {
            stack.push(node);
            node = node.left;
            continue;
        }
        node = stack.pop();// node一定不是null节点，因为上面的if语句保证了只有节点不为空才进栈
        ans.push(node.val);//在leftchild之后加入结果集
        node = node.right;
    }
    return ans;
};

后序遍历

• 递归(easy)

var postorderTraversal = function(root) {
    if (root) {
        postorderTraversal(root.left, arr);
        postorderTraversal(root.right, arr);
        arr.push(root.val);
    }
}

• 迭代
  核心思想:后序遍历需要先遍历左孩子，再遍历右孩子，再遍历根节点。如果迭代按照这个顺序无法在取得右孩子之后获得根节点的值。但是通过观察发现后序遍历是先序遍历的相反操作。从根节点开始，然后遍历右孩子，左孩子，把值从数组的前方插入进数组中，这样就可以保证左孩子的值在右孩子的前面，右孩子的值在根节点值的前面

var postorderTraversal = function(root) {
    let node = root;
    let stack = [];
    let ans = [];
    while (node !== null || stack.length > 0) {
        if (node) {
            ans.unshift(node.val); // 先序遍历相反的操作
            stack.push(node);
            node = node.right; // 先序遍历相反的操作
            continue;
        }
        node = stack.pop();
        node = node.left; // 先序遍历相反的操作
    }
    return ans;
};

层次遍历

   3
   / \
  9  20
    /  \
   15   7
输出 [[3],[9,20],[15,7]]

核心思想:用一个队列记录当前层的节点。用另一个队列记录下一层的节点。对当前层的节点做出队列的操作，保证左孩子在右孩子之前。如果当前节点有左孩子或者右孩子就加入下一层的队列当中。当当前队列已经为空就用下一层的节点来替换，并清空下一层节点的队列以及结果。

var levelOrder = function(root) {
    let ans = [];
    if (root) {
        let queue = [root];
        let nextLevel = [];
        let levelNodes = [];
        while (queue.length > 0) {
            let node = queue.shift();
            if (node) {
                levelNodes.push(node.val);
                node.left && nextLevel.push(node.left);
                node.right && nextLevel.push(node.right);
            }
            if (queue.length === 0) { //当前队列为空，将被赋值下一层的节点，并清空当前层的节点
                ans.push(levelNodes);
                queue = nextLevel;
                nextLevel = [];
                levelNodes = [];
            }
        }
    }
    return ans;
}