《剑指 Offer (第 2 版)》树部分 JavaScript 题解
《剑指 Offer(第 2 版)》通行全球的程序员经典面试秘籍。剖析典型的编程面试题,系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。
最近,把「树」部分的题刷完了。本文来分享下这些题的解法
07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
「示例 1:」
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
「示例 2:」
Input: preorder = [-1], inorder = [-1] Output: [-1]
「限制:」
0 <= 节点个数 <= 5000
题目地址:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
「解题思路」
对于任意一颗树而言,前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。
这样以来,我们就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,我们就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。
/** * 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:
3 / \ 4 5 / \ 1 2
给定的树 B:
4 / 1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
「示例 1:」
输入:A = [1,2,3], B = [3,1] 输出:false
「示例 2:」
输入: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. 二叉树的镜像
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4 / \ 2 7 / \ / \ 1 3 6 9
镜像输出:
4 / \ 7 2 / \ / \ 9 6 3 1
「示例 1:」
输入: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 为根节点的整棵子树的镜像。
/** * 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] 是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
「示例 1:」
输入:root = [1,2,2,3,4,4,3] 输出:true
「示例 2:」
输入: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
返回其层次遍历结果:
[ [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
返回其层次遍历结果:
[ [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」的基础上修改即可
/** * 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。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5 / \ 2 6 / \ 1 3
「示例 1:」
输入: [1,6,3,2,5] 输出: false
「示例 2:」
输入: [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:」
输入: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:」
输入:root = [1,2,3], targetSum = 5 输出:[]
「示例 3:」
输入: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. 二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
题目地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
「解题思路」
二叉搜索树的中序遍历便是升序的,自然而然的,我们便先中序遍历将节点保存下来,然后将他们相连成循环双向链表。
/** * // 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:」
输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 4
「示例 2:」
输入: 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/
「解题思路」
通过逆中序遍历遍历即可
「递归解法」
/** * 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; };
「非递归解法」
/** * 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],
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]
「示例 1:」
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
「示例 2:」
输入: 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 ,则在循环中可减少判断条件。
/** * 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]
「示例 1:」
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
「示例 2:」
输入: 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
返回:
[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; };