二叉树

1、前序遍历

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
递归法

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

迭代法 stack

var preorderTraversal = function(root) {
    let stack = [root]
    let res = []
    while (stack.length) {
        let node = stack.pop()
        //注意，node为空时，不忘stack中push子节点
        if (node) {
            res.push(node.val)
            stack.push(node.right)
            stack.push(node.left)
        }
    }
    return res
};

2、中序遍历

递归法

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

迭代法
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/

var inorderTraversal = function(root) {
    let stack = []
    let res = []
    while (root || stack.length) {
      //重要，将左子树入栈
        while (root) {
            stack.push(root)
            root =  root.left
        }
          //想象根节点的右侧
        root = stack.pop()
        res.push(root.val)
        root = root.right
    }
    return res
};

3、后序遍历

递归法

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

迭代法

var postorderTraversal = function(root) {
    let stack = [root]
    let res = []
    while (stack.length) {
        let node = stack.pop()
        if (node) {
            stack.push(node.left, node.right)
            res.unshift(node.val)
        }
    }
    return res
};

4、层序遍历

递归法
迭代法
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

var inorder = function(root) {
    if (!root) return []
    const res = []
    const que = [root]
    while (que.length) {
        let len = que.length
        let arr = []
        //重点
        while (len--) {
            let node = que.shift()
            arr.push(node.val)
            if (node.right) que.push(node.right)
            if (node.left) que.push(node.left)
        }
        res.push(arr)
    }
    return res
}

5、判断两个二叉树是否相同

递归

6、二叉树的最小深度

7、将有序数组转换为二叉搜索树

解答

8、二叉树的镜像

https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

var mirrorTree = function(root) {
    if (root == null) {
        return null;
    }
    const left = mirrorTree(root.left);
    const right = mirrorTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

9、二叉树的最大深度

var maxDepth = function(root) {
    if (!root) return 0
    return Math.max(maxDepth(root.left), maxDepth(root.right)) +1
};