对称二叉树、二叉树的最大深度和验证二叉搜索树
给定一个二叉树，要判定是否是镜像对称的
示例
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2 2/ \ / \3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1/ \2 2/ \3 3
思路
判断二叉树是不是对称的，主要是看二叉树左边和右边的节点是不是各自相等。所以我们可以通过递归，去判断左树的左节点和右树的右节点是不是相同。如果两个节点都为空，则表示递归到树的底部了；如果有一边空了另外一半没空，说明有一边的节点没了，另外一半还在，肯定不是对称的树；如果两边对称，继续递归节点的左右节点，直到递归完全或者发现不对称。
详解
我们判断当前的树结构还是否为空，为空则该树是对称的，不为空则递归判断左子树的左子树和右子树的右子树是否相等
如果左节点或右节点为空时，则判断对应的右节点或左节点是否为空，为空则返回
true，不为空则返回false如果左右节点都不为空时，则判断左节点的左节点和右节点的右节点是否相等
如果相等，则继续传入该节点的子节点去判断；不相等则直接返回
false
代码
/*** 如果输入一个空对象，则直接返回true* @param {TreeNode} root* @return {boolean}*/const isSymmetric = function (root) {if (!root) {// 若根节点为空，则返回truereturn true;}// 递归函数return isSameTree(root.left, root.right);};/*** 判断二叉树是否对称，直接去判断根节点的左子树和右子树是否相同* @param {TreeNode} root*/const isSameTree = (r, l) => {// 若左节点或右节点为空，则判断对应的右节点或左节点是否为空// 为空时，则返回true，不为空则返回falseif (r === null) return l === null;if (l === null) return r === null;// 判断左节点的左节点和右节点的右节点是否相等// 不相等时，则该树不对称，相等时则继续递归判断if (r.val !== l.val) return false;return isSameTree(r.left, l.right) && isSameTree(r.right, l.left);};
复杂度分析
时间复杂度：
我们需要对这个树中的每个节点都要进行遍历
空间复杂度：
当树是线性时，由栈上的递归调用造成的空间复杂度为
思路
迭代的思路就是不断的把待处理的节点入队，每次都将本级的节点进行判断是否对称，如果不对称则返回false，对称则将下一级的节点全部入栈，然后再依次出队判断处理，再获取新的待处理节点入队，直到结束。
详解
最开始将根节点入列，然后新建一个出队的队列 level，我们对 level 进行判断处理。
我们一次取出 level 队列中下标为 i 和下标为 (level.length - i - 1) 的两个元素进行比较；
若不相等，则返回false；若相等，则将下下一级的节点全部入列，然后在将下一级的节点全部出列进行判断；
重复第 3、4 步，当队列为空时，则方法停止。
代码
/*** 如果输入一个空对象，则直接返回true* @param {TreeNode} root* @return {boolean}*/const isSymmetric = function (root) {if (!root) return true;const queue = [root.left, root.right];while (queue.length) {let len = queue.length;const level = [];while (len) {// 出列const pop = queue.shift();level.push(pop);if (pop) {// 入列queue.push(pop.left);queue.push(pop.right);}len--;}// 判断该层级的所有节点是否是对称的for (let i = 0, l = level.length; i < l / 2; i++) {// 一个为null，一个不为null的则该节点不对称// 返回fasleif (level[i] === null && level[l - i - 1] !== null) return false;if (level[i] !== null && level[l - i - 1] === null) return false;// 两个都不是null的情况// 节点不相等 返回falseif (level[i] !== null && level[l - i - 1] !== null) {if (level[i].val !== level[l - i - 1].val) return false;}}}return true;};
复杂度分析
时间复杂度：
空间复杂度：
当树是线性时，我们可能需要向队列中插入 个节点
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例
给定二叉树 [3, 9, 20, null, null, 15, 7]，
3/ \9 20/ \15 7
返回它的最大深度 3。
思路
遍历所有节点的深度，记录所有子节点的深度，然后筛选出最大的深度
详解
创建一个空数组用来保存所有节点深度
判断二叉树是否为空，空的直接返回 0，结束，非空二叉树继续
遍历二叉树节点，没有左右子节点的，直接将当前 level 塞入之前定义的深度数组
有左右子节点的就继续递归查询查询子节点的深度，传入的 level 也加 1 传递，直到二叉树遍历结束
对深度数组排序返回最大值，也就是二叉树最大深度
代码
const maxDepth = function (root) {// 创建保存节点深度的空数组const levelList = [];// 判断二叉树是否为空if (root === null) {return 0;} else {loop(root, 1);return sort(levelList);}// 遍历二叉树子节点function loop (node, level) {// 没有子节点的，将当前深度保存进深度数组，有节点的继续遍历if (node.left === null && node.right === null) {levelList.push(level);} else if (node.left !== null) {loop(node.left, level + 1);} if (node.right !== null) {loop(node.right, level + 1);}}// 对数组进行排序，返回最大深度function sort (arr) {arr.sort((a, b) => {return b - a;});return arr[0];}};
复杂度分析
时间复杂度：
空间复杂度：
思路
递归二叉树的节点，获取左子树和右子树的最大深度，比较后，返回最大深度
详解
判断二叉树是否为空，空的直接返回 0，结束，非空二叉树继续
分别递归计算左右子树的最大深度
根据返回两者的两者数字，比较后的返回二叉树的最大深度
代码
const maxDepth = function (root) {if (root === null) {return 0;} else {const leftDepth = maxDepth(root.left);const rightDepth = maxDepth(root.right);const childDepth = leftDepth > rightDepth ? leftDepth : rightDepth;return 1 + childDepth;}};
复杂度分析
时间复杂度：
通过递归的方式查询了数的所有子节点。查询花费 的时间。
空间复杂度：
每次递归都需要创建新的临时空间，空间复杂度
