给定一个二叉树,要判定是否是镜像对称的
示例
例如,二叉树 [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;}};
复杂度分析
时间复杂度:
通过递归的方式查询了数的所有子节点。查询花费 的时间。
空间复杂度:
每次递归都需要创建新的临时空间,空间复杂度