对称二叉树、二叉树的最大深度和验证二叉搜索树

对称二叉树

给定一个二叉树,要判定是否是镜像对称的

示例

例如,二叉树 [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

方法一 递归判断

思路

判断二叉树是不是对称的,主要是看二叉树左边和右边的节点是不是各自相等。所以我们可以通过递归,去判断左树的左节点和右树的右节点是不是相同。如果两个节点都为空,则表示递归到树的底部了;如果有一边空了另外一半没空,说明有一边的节点没了,另外一半还在,肯定不是对称的树;如果两边对称,继续递归节点的左右节点,直到递归完全或者发现不对称。

详解

  1. 我们判断当前的树结构还是否为空,为空则该树是对称的,不为空则递归判断左子树的左子树和右子树的右子树是否相等

  2. 如果左节点或右节点为空时,则判断对应的右节点或左节点是否为空,为空则返回 true,不为空则返回 false

  3. 如果左右节点都不为空时,则判断左节点的左节点和右节点的右节点是否相等

  4. 如果相等,则继续传入该节点的子节点去判断;不相等则直接返回 false

代码

/**
* 如果输入一个空对象,则直接返回true
* @param {TreeNode} root
* @return {boolean}
*/
const isSymmetric = function (root) {
if (!root) {
// 若根节点为空,则返回true
return true;
}
// 递归函数
return isSameTree(root.left, root.right);
};
/**
* 判断二叉树是否对称,直接去判断根节点的左子树和右子树是否相同
* @param {TreeNode} root
*/
const isSameTree = (r, l) => {
// 若左节点或右节点为空,则判断对应的右节点或左节点是否为空
// 为空时,则返回true,不为空则返回false
if (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);
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    我们需要对这个树中的每个节点都要进行遍历

  • 空间复杂度:O(n)O(n)

    当树是线性时,由栈上的递归调用造成的空间复杂度为 O(n)O(n)

方法二 迭代判断

思路

迭代的思路就是不断的把待处理的节点入队,每次都将本级的节点进行判断是否对称,如果不对称则返回false,对称则将下一级的节点全部入栈,然后再依次出队判断处理,再获取新的待处理节点入队,直到结束。

详解

  1. 最开始将根节点入列,然后新建一个出队的队列 level,我们对 level 进行判断处理。

  2. 我们一次取出 level 队列中下标为 i 和下标为 (level.length - i - 1) 的两个元素进行比较;

  3. 若不相等,则返回false;若相等,则将下下一级的节点全部入列,然后在将下一级的节点全部出列进行判断;

  4. 重复第 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的则该节点不对称
// 返回fasle
if (level[i] === null && level[l - i - 1] !== null) return false;
if (level[i] !== null && level[l - i - 1] === null) return false;
// 两个都不是null的情况
// 节点不相等 返回false
if (level[i] !== null && level[l - i - 1] !== null) {
if (level[i].val !== level[l - i - 1].val) return false;
}
}
}
return true;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(n)O(n)

    当树是线性时,我们可能需要向队列中插入 O(n)O(n) 个节点

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例

给定二叉树 [3, 9, 20, null, null, 15, 7],

3
/ \
9 20
/ \
15 7

返回它的最大深度 3。

方法一 递归查询排序

思路

遍历所有节点的深度,记录所有子节点的深度,然后筛选出最大的深度

详解

  1. 创建一个空数组用来保存所有节点深度

  2. 判断二叉树是否为空,空的直接返回 0,结束,非空二叉树继续

  3. 遍历二叉树节点,没有左右子节点的,直接将当前 level 塞入之前定义的深度数组

  4. 有左右子节点的就继续递归查询查询子节点的深度,传入的 level 也加 1 传递,直到二叉树遍历结束

  5. 对深度数组排序返回最大值,也就是二叉树最大深度

代码

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];
}
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

  • 空间复杂度:O(n)O(n)

方法二 递归

思路

递归二叉树的节点,获取左子树和右子树的最大深度,比较后,返回最大深度

详解

  1. 判断二叉树是否为空,空的直接返回 0,结束,非空二叉树继续

  2. 分别递归计算左右子树的最大深度

  3. 根据返回两者的两者数字,比较后的返回二叉树的最大深度

代码

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;
}
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    通过递归的方式查询了数的所有子节点。查询花费 O(n)O(n) 的时间。

  • 空间复杂度:O(n)O(n)

    每次递归都需要创建新的临时空间,空间复杂度 O(n)O(n)