2.1 二叉树

• 2.1.1 二叉树的遍历
• 2.1.2 二叉树的层序遍历

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。

二叉树拥有一个根节点，每个节点至多拥有两个子节点，分别为：左节点和右节点。树的最底部节点称之为叶节点。

当一颗树的叶数量数量为满时，该树可以称之为满二叉树。

2.1.1 二叉树的遍历

先序遍历--先访问根节点，然后遍历左子树，最后遍历右子树

根 - 左 - 右

F - B - A - D - C - E - G - I - H

中序遍历--先遍历左子树，然后访问根节点，然后遍历右子树

左 - 根 - 右

A - B - C - D - E - F - G - H - I

后序遍历--先遍历左子树，然后遍历右子树，最后访问树的根节点

左 - 右 - 根

A - C - E - D - B - H - I - G - F

这三种遍历也叫做深度优先遍历。

深度优先：把某一边遍历完再说。

先序遍历 (opens new window)

// 先序遍历
// 利用栈
var preorderTraversal = function(root) {
    let myStack = new Stack();
    let res = [];
    root && myStack.push(root);
    while(myStack.getSize() > 0) {
        let cur = myStack.pop();
        res.push(cur.val);
        cur.right && myStack.push(cur.right);
        cur.left && myStack.push(cur.left);
    }
    return res;
};

// 递归法
var preorderTraversal = function(root) {
    const res = [];
    set(root);
    return res;
    function set(tree) {
        if (!tree) return;
        res.push(tree.val);
        tree.left && set(tree.left);
        tree.right && set(tree.right);
    }
};

2.1.2 二叉树的层序遍历

层序遍历（广度优先遍历）就是逐层遍历树结构。

从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。


F - B - G - A - D - I - C - E - H

F - B - A - D - C - E -G - I - H

层序遍历 (opens new window)

// 层序遍历
// 先访问根就对了
var levelOrder = function(root) {
    const res = [];
    set(root, 0);
    return res;
    function set(tree, count) {
        if (!tree) return;
        if (!Array.isArray(res[count])) res[count] = [];
        res[count].push(tree.val);
        tree.left && set(tree.left, count + 1);
        tree.right && set(tree.right, count + 1);
    }
};