《剑指 Offer (第 2 版)》树部分 JavaScript 题解
《剑指 Offer(第 2 版)》通行全球的程序员经典面试秘籍。剖析典型的编程面试题,系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。
最近,把「树」部分的题刷完了。本文来分享下这些题的解法
07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
「示例 1:」
代码语言:javascript复制Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
「示例 2:」
代码语言:javascript复制Input: preorder = [-1], inorder = [-1]
Output: [-1]
「限制:」
0 <= 节点个数 <= 5000
题目地址:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
「解题思路」
对于任意一颗树而言,前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。
这样以来,我们就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,我们就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。
代码语言:javascript复制/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
if (preorder.length === 0) return null;
if (preorder === 1) return new TreeNode(preorder[0]);
function build(preorderStart, preorderEnd, inorderStart, inorderEnd) {
const root = new TreeNode(preorder[preorderStart]);
const rootIndex = inorder.indexOf(preorder[preorderStart]);
root.left = rootIndex === inorderStart ? null :
build(preorderStart 1, preorderStart rootIndex - inorderStart, inorderStart, rootIndex - 1);
root.right = rootIndex === inorderEnd ? null :
build(preorderStart rootIndex - inorderStart 1, preorderEnd, rootIndex 1, inorderEnd);
return root;
}
return build(0, preorder.length - 1, 0, inorder.length - 1);
};
26. 树的子结构
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如: 给定的树 A:
代码语言:javascript复制 3
/
4 5
/
1 2
给定的树 B:
代码语言:javascript复制 4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
「示例 1:」
代码语言:javascript复制输入:A = [1,2,3], B = [3,1]
输出:false
「示例 2:」
代码语言:javascript复制输入:A = [3,4,5,1,2], B = [4,1]
输出:true
「限制:」
0 <= 节点个数 <= 10000
题目地址:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
「解题思路」
递归,主要分为是否是子树,和两树是否相同 两个函数
- 对于两树是否相同 :如果A或B有一个是空的,那肯定不相同;然后判断A和B是否相同、A的左子树和B是否相同、A的右子树和B是否相同。
- 对于是否是子树:先判断B,如果空了说明遍历完了,是子树,返回true;再判断A,如果在B没空的前提下A空了,说明不是子树;然后判断值;最后继续递归各自左子树、右子树。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} A
* @param {TreeNode} B
* @return {boolean}
*/
var isSubStructure = function(A, B) {
if (!A || !B) return false;
return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};
function isSame(A, B) {
// B空了,说明B树遍历完了,是子树
if(!B)
return true;
// 不符合上面情况的前提下A空了,说明B树还没遍历完,不是子树
if(!A)
return false;
// 值不同,不是子树
if(A.val !== B.val)
return false;
return isSame(A.left, B.left) && isSame(A.right, B.right);
}
27. 二叉树的镜像
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
代码语言:javascript复制 4
/
2 7
/ /
1 3 6 9
镜像输出:
代码语言:javascript复制 4
/
7 2
/ /
9 6 3 1
「示例 1:」
代码语言:javascript复制输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
「限制:」
0 <= 节点个数 <= 1000
题目地址:https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
「解题思路」
我们从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root 的左右两棵子树都已经翻转得到镜像,那么我们只需要交换两棵子树的位置,即可得到以 root 为根节点的整棵子树的镜像。
代码语言:javascript复制/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var mirrorTree = function(root) {
if (!root) return null;
[root.left, root.right] = [root.right, root.left];
mirrorTree(root.left);
mirrorTree(root.right);
return root;
};
28. 对称的二叉树
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
代码语言:javascript复制 1
/
2 2
/ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
代码语言:javascript复制 1
/
2 2
3 3
「示例 1:」
代码语言:javascript复制输入:root = [1,2,2,3,4,4,3]
输出:true
「示例 2:」
代码语言:javascript复制输入:root = [1,2,2,null,3,null,3]
输出:false
「限制:」
0 <= 节点个数 <= 1000
题目地址:https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
「解题思路」
- 对称二叉树定义:对于树中 任意两个对称节点 L 和 R ,一定有:
- L.val = R.val :即此两对称节点值相等。L.left.val = R.right.val :即 L 的 左子节点 和 R 的 右子节点 对称;L.right.val = R.left.val :即 L 的 右子节点 和 R 的 左子节点 对称。
- 根据以上规律,考虑从顶至底递归,判断每对节点是否对称,从而判断树是否为对称二叉树。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
return root === null || isSame(root.left, root.right);
};
function isSame(left, right) {
if (left === null && right === null) return true;
if ((!left && right) || (left && !right)) return false;
return left.val === right.val && isSame(left.left, right.right) && isSame(left.right, right.left);
}
32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7]
,
3
/
9 20
/
15 7
返回其层次遍历结果:
代码语言:javascript复制[
[3],
[9,20],
[15,7]
]
「提示:」
节点总数 <= 1000
题目地址:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
「解题思路」
- 「按层打印」:题目要求的二叉树的 从上至下 打印(即按层打印),又称为二叉树的 「s」(BFS)。BFS 通常借助 队列 的先入先出特性来实现。
- 「每层打印到一行」:将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const result = [[root.val]];
let node = root;
const queue = [root];
while(queue.length) {
const s = [], res = [];
while(queue.length) {
node = queue.shift();
if (node.left) {
s.push(node.left);
res.push(node.left.val);
}
if (node.right) {
s.push(node.right);
res.push(node.right.val);
}
}
if (res.length) {
result.push(res);
queue.push(...s);
}
}
return result;
};
32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如: 给定二叉树: [3,9,20,null,null,15,7]
,
3
/
9 20
/
15 7
返回其层次遍历结果:
代码语言:javascript复制[
[3],
[20,9],
[15,7]
]
「提示:」
节点总数 <= 1000
题目地址:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
「解题思路」
在上题「32 - II. 从上到下打印二叉树 II」的基础上修改即可
代码语言:javascript复制/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if (!root) return [];
const result = [[root.val]];
let node = root;
const queue = [root];
while(queue.length) {
const s = [], res = [];
while(queue.length) {
node = queue.shift();
if (node.left) {
s.push(node.left);
res.push(node.left.val);
}
if (node.right) {
s.push(node.right);
res.push(node.right.val);
}
}
if (res.length) {
result.push(result.length % 2 ? res.reverse() : res);
queue.push(...s);
}
}
return result;
};
33. 二叉搜索树的后序遍历序列
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
代码语言:javascript复制 5
/
2 6
/
1 3
「示例 1:」
代码语言:javascript复制输入: [1,6,3,2,5]
输出: false
「示例 2:」
代码语言:javascript复制输入: [1,3,2,6,5]
输出: true
「提示:」
数组长度 <= 1000
题目地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
「解题思路」
- 二叉搜索树一个特性就是:左子树比根节点小,右子树比根节点大
- 只要找到左右子树的分界点,然后递归的去判定就好了
- 中途有任何不满足的就直接返回
false
就ok
/**
* @param {number[]} postorder
* @return {boolean}
*/
var verifyPostorder = function(postorder) {
function verify(start, end) {
if (start > end) return true;
let mid1 = start;
while(postorder[mid1] < postorder[end]) {
mid1 ;
}
let mid2 = end - 1;
while(postorder[mid2] > postorder[end]) {
mid2 --;
}
return mid1 - 1 === mid2 && verify(start, mid1 - 1) && verify(mid1, end - 1);
}
return verify(0, postorder.length - 1);
};
34. 二叉树中和为某一值的路径
给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
「示例 1:」
image-20220228154909908
代码语言:javascript复制输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
「示例 2:」
image-20220228154944915
代码语言:javascript复制输入:root = [1,2,3], targetSum = 5
输出:[]
「示例 3:」
代码语言:javascript复制输入:root = [1,2], targetSum = 0
输出:[]
「提示:」
- 树中节点总数在范围
[0, 5000]
内 -1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
题目地址:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
「解题思路」
「深度优先遍历」
- 每层都三个参数,一个是当前结点,一个是 target 剩余值,一个是总路径数组
- 当往二叉树深处进行遍历时,如果 target 剩余值跟结点值相等且左右子树为空(叶子结点),则满足要求,往 result 压入当前总路径数组 path
- 对于左右子树不为空的结点,继续往左或右子树进行遍历,直到叶子结点
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} target
* @return {number[][]}
*/
var pathSum = function(root, target) {
if (!root) return [];
const res = [];
const dfs = (root, sum, path) => {
if(!root) return;
// 到了叶子节点并且当前节点的值跟剩余sum相等,则推入结果集中
if (root.val === sum && !root.left && !root.right) {
res.push(path);
}
// 路径中加入当前节点的值
path.push(root.val);
dfs(root.left, sum - root.val, path.slice());
dfs(root.right, sum - root.val, path.slice());
};
dfs(root, target, []);
return res;
};
36. 二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
image-20220225152820584
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
image-20220225152834621
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
题目地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
「解题思路」
二叉搜索树的中序遍历便是升序的,自然而然的,我们便先中序遍历将节点保存下来,然后将他们相连成循环双向链表。
代码语言:javascript复制/**
* // Definition for a Node.
* function Node(val,left,right) {
* this.val = val;
* this.left = left;
* this.right = right;
* };
*/
/**
* @param {Node} root
* @return {Node}
*/
var treeToDoublyList = function(root) {
if (root === null) return null;
const stk = [], nodeList = [];
let node = root;
while(stk.length || node) {
while(node) {
stk.push(node);
node = node.left;
}
node = stk.pop();
nodeList.push(node);
node = node.right;
}
nodeList.push(nodeList[0]);
for(let i = 1; i < nodeList.length - 1; i ) {
nodeList[i].right = nodeList[i 1];
nodeList[i].left = nodeList[i - 1];
}
nodeList[0].right = nodeList[1];
nodeList[0].left = nodeList[nodeList.length - 2];
return nodeList[0];
};
54. 二叉搜索树的第k大节点
给定一棵二叉搜索树,请找出其中第 k
大的节点的值。
「示例 1:」
代码语言:javascript复制输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 4
「示例 2:」
代码语言:javascript复制输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
输出: 4
「限制:」
- 1 ≤ k ≤ 二叉搜索树元素个数
题目地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
「解题思路」
通过逆中序遍历遍历即可
「递归解法」
代码语言:javascript复制/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthLargest = function (root, k) {
let node;
if (!root) return node;
const dfs = (root) => {
if (!root) return null;
dfs(root.right);
k--;
if (!k) return (node = root.val);
dfs(root.left);
};
dfs(root);
return node;
};
「非递归解法」
代码语言:javascript复制/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthLargest = function(root, k) {
const stack = [];
let node = root;
while(node || stack.length) {
while(node) {
stack.push(node);
node = node.right;
}
node = stack.pop();
k --;
if (!k) return node.val;
node = node.left;
}
};
55 - I. 二叉树的深度
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
例如:
给定二叉树 [3,9,20,null,null,15,7],
代码语言:javascript复制 3
/
9 20
/
15 7
返回它的最大深度 3 。
「提示:」
节点总数 <= 10000
题目地址:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
「解题思路」
- 递归的终止条件是遍历到叶子结点
- 递归的返回值是 左子树深度 和 右子树深度 更大的那个 1(因为左右子树有个共同父亲,所以深度上得再加个1)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) 1;
};
55 - II. 平衡二叉树
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
「示例 1:」
给定二叉树 [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 2
/
3 3
/
4 4
返回 false
。
「限制:」
0 <= 树的结点个数 <= 10000
题目地址:https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
「解题思路」
首先先定义计算节点高度的函数maxDepth
(题55 - I. 二叉树的深度),即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历,即对于当前遍历到的节点,首先计算左右子树的高度,如果左右子树的高度差是否不超过 1,再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
if (!root) return true;
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};
var maxDepth = function(root) {
if (!root) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) 1;
};
68 - I. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(「一个节点也可以是它自己的祖先」)。”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
image-20220301123336763
「示例 1:」
代码语言:javascript复制输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
「示例 2:」
代码语言:javascript复制输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
「说明:」
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
题目地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
「解题思路」
「祖先的定义:」 若节点 p 在节点 root 的左(右)子树中,或 p = root,则称 root 是 p 的祖先。
「最近公共祖先的定义」:设节点 root 为节点 p,q 的某公共祖先,若其左子节点 root.left和右子节点 root.right 都不是 p,q 的公共祖先,则称 root 是 “最近的公共祖先” 。
根据以上定义,若 root 是 p,q 的 最近公共祖先 ,则只可能为以下情况之一:
- p 和 q 在 root 的子树中,且分列 root 的 异侧(即分别在左、右子树中);
- p = root,且 q 在 root 的左或右子树中;
- q = root,且 p 在 root 的左或右子树中;
本题给定了两个重要条件:① 树为 二叉搜索树 ,② 树的所有节点的值都是 唯一 的。根据以上条件,可方便地判断 p,q 与 root 的子树关系,即:
- 若 root.val < p.val ,则 p 在 root 右子树 中;
- 若 root.val > p.val ,则 p 在 root 左子树 中;
- 若 root.val = p.val ,则 p 和 root 指向 同一节点 。
「方法一:迭代」
- 「循环搜索」:当节点 root 为空时跳出;
- 当 p, q都在 root 的 「右子树」 中,则遍历至 root.right ;
- 否则,当 p, q 都在 root 的 「左子树」 中,则遍历至 root.left ;
- 否则,说明找到了 「最近公共祖先」 ,跳出。
- 「返回值」:最近公共祖先 root 。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
while(root) {
if (root.val > p.val && root.val > q.val) {
root = root.left;
} else if (root.val < p.val && root.val < q.val) {
root = root.right;
} else {
return root;
}
}
};
优化:若可保证 p*.val<q.*val ,则在循环中可减少判断条件。
代码语言:javascript复制/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if (p.val > q.val) {
[p, q] = [q, p];
}
while(root) {
if (root.val > q.val) {
root = root.left;
} else if (root.val < p.val) {
root = root.right;
} else {
return root;
}
}
};
「方法二:递归」
- 「递推工作」:
- 当 p, q 都在 root 的 「右子树」 中,则开启递归 root.right 并返回;
- 否则,当 p, q 都在 root 的 「左子树」 中,则开启递归 root.left 并返回;
- 「返回值」:最近公共祖先 root 。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
while(root) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
};
68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
image-20220301142043674
「示例 1:」
代码语言:javascript复制输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
「示例 2:」
代码语言:javascript复制输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
「说明:」
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
题目地址:https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
「解题思路」
- 先给出递归函数的定义:给该函数输入三个参数 root,p,q,它会返回一个节点
- 如果 p 和 q 都在以 root 为根的树中,函数返回的就是 p 和 q 的最近公共祖先节点。
- 那如果 p 和 q 都不在以 root 为根的树中怎么办呢?函数理所当然地返回 null 呗。
- 那如果 p 和 q 只有一个存在于 root 为根的树中呢?函数就会返回那个节点。
- 根据这个定义,分情况讨论:
- 如果 p 和 q 都在以 root 为根的树中,那么 left 和 right 一定分别是 p 和 q(从 base case 看出来的)。
- 如果 p 和 q 都不在以 root 为根的树中,直接返回 null。
- 如果 p 和 q 只有一个存在于 root 为根的树中,函数返回该节点。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
// 遇到null,返回null 没有LCA
if (root == null) return null;
// 遇到p或q,直接返回当前节点
if (root == q || root == p) return root;
// 非null 非q 非p,则递归左右子树
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// 根据递归的结果,决定谁是LCA
if (left && right) return root;
if (left == null && right == null) return null;
return left == null ? right : left;
};
面试题32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如: 给定二叉树: [3,9,20,null,null,15,7]
,
3
/
9 20
/
15 7
返回:
代码语言:javascript复制[3,9,20,15,7]
「提示:」
节点总数 <= 1000
题目地址:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
「解题思路」
- 题目要求的二叉树的 「从上至下」 打印(即按层打印),又称为二叉树的 「广度优先搜索」(BFS)。
- BFS 通常借助 「队列」 的先入先出特性来实现。
- 「特例处理」:当树的根节点为空,则直接返回空列表
[]
; - 「初始化」:打印结果列表
result = []
,包含根节点的队列queue = [root]
; - 「BFS 循环」:当队列
queue
为空时跳出;- 「出队」:队首元素出队,记为
node
; - 「打印」:将
node.val
添加至列表尾部; - 「添加子节点」:若
node
的左(右)子节点不为空,则将左(右)子节点加入队列queue
;
- 「出队」:队首元素出队,记为
- 「返回值」:返回打印结果列表
result
即可。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var levelOrder = function(root) {
if (!root) return [];
const queue = [root], result = [];
while(queue.length) {
const node = queue.shift();
result.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
return result;
};