二叉树

壹｜什么是二叉树

二叉树有两个子节点，并不要求每个节点都有两个子节点。
满二叉树是每个节点都有两个子节点。
完全二叉树是除了最后一层，上面是满二叉树，且最后一层节点都靠左对齐。
二叉搜索树是一个有序树。左子树节点的值小于跟节点的值，右子树的值大于跟节点的值。
平衡二叉搜索树是二叉搜索树，且两个子树高度差不超过1。

贰｜二叉树的遍历

深度优先遍历

• 前序遍历
• 中序遍历
• 后续遍历 ```javascript 前序遍历递归： var preorderTraversal = function(root) { let res = []; const dfs = function(root){ if(root === null) return; res.push(root.val); dfs(root.left); dfs(root.right); } dfs(root); return res; };

前序遍历迭代： var preorderTraversal = function(root, res = []) { if(!root) return res; const stack = [root]; let cur = null; while(stack.length) { cur = stack.pop(); res.push(cur.val); cur.right && stack.push(cur.right); cur.left && stack.push(cur.left); } return res; };

中序遍历递归： var inorderTraversal = function(root) { let res = []; const dfs = function(root){ if(root === null){ return ; } dfs(root.left); res.push(root.val); dfs(root.right); } dfs(root); return res; };

中序遍历迭代： var inorderTraversal = function(root, res = []) { const stack = []; let cur = root; while(stack.length || cur) { if(cur) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); res.push(cur.val); cur = cur.right; } }; return res; };

后序遍历递归： var postorderTraversal = function(root) { let res = []; const dfs = function(root){ if(root === null){ return ; } dfs(root.left); dfs(root.right); res.push(root.val); } dfs(root); return res; };

后序遍历迭代： var postorderTraversal = function(root, res = []) { if (!root) return res; const stack = [root]; let cur = null; do { cur = stack.pop(); res.push(cur.val); cur.left && stack.push(cur.left); cur.right && stack.push(cur.right); } while(stack.length); return res.reverse(); };

<a name="Vimln"></a>
### 广度优先遍历
- 层次遍历
```javascript
var levelOrder = function(root) {
    let res = [],queue = [];
    queue.push(root);
    if(root === null){
        return res;
    }
    while(queue.length){
        let length = queue.length;
        let curLevel = [];
        for(let i = 0; i < length; i++){
            let node = queue.shift();
            curLevel.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(curLevel);
    }
    return res;
};