本文最后更新于：2023年3月19日 晚上
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先、剑指 Offer 52. 两个链表的第一个公共节点、剑指 Offer 55 - II. 平衡二叉树、剑指 Offer 28. 对称的二叉树
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
1
2
3
| 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
|
示例 2:
1
2
3
| 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
|
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
思路
结合二叉搜索树的特点，当当前节点值都比 p、q 要大的时候，说明公共节点在左边，返回左子树，都要小的时候说明公共节点在右边，返回右子树。当值在两个之间时，就为公共祖先。
吐槽一下力扣，这题不能使用 js 写，ts 返回结构限制为 TreeNode，期望得到的答案却是 number :)。所以贴一下主站 235 的答案。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
var lowestCommonAncestor = function (root, p, q) {
if (!root) return null;
if (root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
return root;
};
|
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
1
2
3
| 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
|
示例 2：
1
2
3
| 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
|
示例 3：
1
2
3
4
| 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
|
注意：
思路
暴力双重循环
很容易可以得到一种解法，双重遍历比较 a、b 每个节点的 next 是否相等，相等即可直接返回
哈希表
若没有限制空间复杂度为 O(1)，可以使用 hash 表进行判断，则满足 O(n)的时间复杂度要求
双指针法
设交集链表长 c,链表 1 除交集的长度为 a，链表 2 除交集的长度为 b，有
- a + c + b = b + c + a
- 若无交集，则 a + b = b + a
所以当 tmpA 或 tmpB 为空时，将他们设置为另一条链的头结点，再走不是交集的那个长度，最后一定会在交点处遇上
解答
暴力双重循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
var getIntersectionNode = function (headA, headB) {
let tmpA = headA;
let tmpB = headB;
while (tmpA && tmpB) {
let tmp = tmpB;
while (tmp) {
if (tmpA === tmp) return tmpA;
tmp = tmp.next;
}
tmpA = tmpA.next;
}
return null;
};
|
哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
var getIntersectionNode = function (headA, headB) {
let map = new Map();
while (headA) {
map.set(headA, true);
headA = headA.next;
}
while (headB) {
if (map.get(headB)) return headB;
headB = headB.next;
}
return null;
};
|
双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
var getIntersectionNode = function (headA, headB) {
let tmpA = headA,
tmpB = headB;
while (tmpA != tmpB) {
tmpA = tmpA ? tmpA.next : headA;
tmpB = tmpB ? tmpB.next : headB;
}
return tmpA;
};
|
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。
示例 1:
1
2
3
4
5
6
7
| 给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
|
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
2
3
4
5
6
7
8
| 1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
|
限制：
注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/
思路
本题结合了求树的最大深度，对每一个节点返回其左右子树的最大深度，判断他们的绝对值是否大于 1，大于即返回 false。再递归计算树里的每一个节点是否都符合这个规则即可。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
var isBalanced = function (root) {
if (!root) return true;
return (
Math.abs(getDeep(root.left) - getDeep(root.right)) <= 1 &&
isBalanced(root.left) &&
isBalanced(root.right)
);
};
const getDeep = (root) => {
if (!root) return 0;
return Math.max(1 + getDeep(root.left), 1 + getDeep(root.right));
};
|
难度简单 83 收藏分享切换为英文关注反馈
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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：
1
2
| 输入：root = [1,2,2,3,4,4,3]
输出：true
|
示例 2：
1
2
| 输入：root = [1,2,2,null,3,null,3]
输出：false
|
限制：
0 <= 节点个数 <= 1000
注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/
思路
写一个判断是否相等的函数。传入树 1 和树 2，如果两个都为空则返回 true 结束递归，如果有一个为空或者两个节点的值不相等则不满足情况返回 false。传入两个节点的值应该相等，同时他们的左右节点应该互相相等才符合对称。不断递归计算即可。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
var isSymmetric = function (root) {
return isSame(root, root);
};
const isSame = (tree1, tree2) => {
if (!tree1 && !tree2) return true;
if ((!tree1 && tree2) || (tree1 && !tree2)) return false;
if (tree1.val === tree2.val)
return isSame(tree1.left, tree2.right) && isSame(tree1.right, tree2.left);
return false;
};
|
