在郑州网站建设,hexo wordpress 主题,旅游微网站建设,科讯网站首页公告模板这是一道 中等难度 的题 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为… 这是一道 中等难度 的题 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
示例 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 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3
输入root [1,2], p 1, q 2
输出1 提示
树中节点数目在范围 [ 2 , 1 0 5 ] [2, 10^5] [2,105] 内。 − 1 0 9 N o d e . v a l 1 0 9 -10^9 Node.val 10^9 −109Node.val109所有 N o d e . v a l Node.val Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。 题解
公共祖先的定义以这个节点为根节点的二叉树中同时包含有 节点p 和 节点q。
判断一颗树是否包含 节点p 只要满足以下条件中的一个即可
根节点就是 节点p。左子树包含 节点p。右子树包含 节点p。
很明显的可以看出条件2和3是这个问题的子问题首先考虑递归的思路去实现。
以 Java 代码为例
private boolean dfs(TreeNode node, TreeNode p){// 边界条件if(node null){return false;}// 满足条件1if(node p){return true;}// 满足 条件2 或 条件3return dfs(node.left) || dfs(node.right);
}同样的判断是否包含 节点q 也是上面的逻辑。
因为判定是否是公共祖先需要同时判定是否包含 节点p 和 节点q所以需要对上面的递归函数稍微改进一下。
我们可以让递归函数返回一个 boolean 数组 has[]来表示是否包含节点p 和 节点q其中 h a s [ 0 ] t r u e has[0] true has[0]true 表示包含 节点p h a s [ 0 ] f a l s e has[0] false has[0]false 表示不包含。 h a s [ 1 ] t r u e has[1] true has[1]true 表示包含 节点q h a s [ 1 ] f a l s e has[1] false has[1]false 表示不包含。
改进后的代码实现为
private boolean[] dfs(TreeNode node, TreeNode p, TreeNode q){boolean[] has new boolean[2];// 边界条件if(node null){return hase;}// 满足条件1if(node p){has[0] true;}if(node q){has[1] true;}boolean[] leftHas dfs(node.left, p, q);boolean[] rightHas dfs(node.left, p, q);// 满足 条件2 或 条件3has[0] has[0] || leftHas[0] || rightHas[0];has[1] has[1] || leftHas[1] || rightHas[1];// 只要满足 has[0] 和 has[1] 都为true// 就说明这个节点 node 是节点 p 和 q 的公共祖先。return has;
}通过上述递归函数我们可以求得 节点p 和 节点q 的所有公共祖先但是题目要求的是求得 最近公共祖先。
最近公共祖先的定义所有公共祖先当中深度最大的那个即为最近公共祖先。
因为递归函数是从上往下递归的答案的得出是从下往上回溯的。所以最先知道其是公共祖先的那个节点就是最近公共祖先。
假设答案为 ans当知道节点 node 是公共祖先且 ans 为空 的时候节点 node 就是答案。因为 ans 不空的时候node 已经不是最深处的那个公共祖先了。
完整代码见代码实现。
Java 代码实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {private TreeNode ans null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root, p, q);return ans;}private boolean[] dfs(TreeNode node, TreeNode p, TreeNode q){boolean[] has new boolean[2];// 边界条件if(node null){return has;}// 满足条件1if(node p){has[0] true;}if(node q){has[1] true;}boolean[] leftHas dfs(node.left, p, q);boolean[] rightHas dfs(node.right, p, q);// 满足 条件2 或 条件3has[0] has[0] || leftHas[0] || rightHas[0];has[1] has[1] || leftHas[1] || rightHas[1];// 最先知道答案的即为最近公共祖先if(ans null has[0] has[1]){ans node;}return has;}}Go 代码实现
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {var ans *TreeNodevar dfs func(node *TreeNode) []booldfs func(node *TreeNode) []bool {has : []bool{false, false}if node nil {return has}if node p {has[0] true}if node q {has[1] true}leftHas : dfs(node.Left)rightHas : dfs(node.Right)has[0] has[0] || leftHas[0] || rightHas[0]has[1] has[1] || leftHas[1] || rightHas[1]if ans nil has[0] has[1] {ans node}return has}dfs(root)return ans}复杂度分析
时间复杂度 O ( N ) O(N) O(N)N 为二叉树中节点的个数每个节点都需要遍历一次。
空间复杂度 O ( N ) O(N) O(N)N 为二叉树中节点的个数空间复杂度取决于递归调用栈的深度最大为 N。
