湘潭网站建设 沟通磐石网络,开一个网站需要什么手续,关键词优化如何,wordpress如何加载ppt难度等级#xff1a;中等 上一篇算法#xff1a; 103. 二叉树的锯齿形层序遍历【191】 力扣此题地址#xff1a; 236. 二叉树的最近公共祖先 - 力扣#xff08;Leetcode#xff09; 1.题目#xff1a;236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点… 难度等级中等 上一篇算法 103. 二叉树的锯齿形层序遍历【191】 力扣此题地址 236. 二叉树的最近公共祖先 - 力扣Leetcode 1.题目236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 2.解题思路 自顶向下遍历用递归的方法这里找到公共祖先分为两种情况 1.p 和 q 在公共结点的两侧则当前结点就是公共结点 2.公共结点为p 或 q 中的任何一个另一个则为公共结点的子节点那么p 或 q 则是公共结点。 代码思路 1先判断root是否为null或者root 为p 或 q中的任意一个那么直接返回root这里的root放在递归的时候就是当前结点。root为null有两种情况一种是树为null第二种是叶子结点为null也就是遍历完了也没找到目标值 2既然p 或 q 不是公共结点那么分别递归左子树和右子树 3如果左子树和右子树都为null说明左子树和右子树都遍历到叶子结点了也没有找到目标值那么返回null 4如果左子树为null说明左子树没有目标值那就返回右子树结果反之亦然 5左子树和右子树都找到了目标结点那就返回当前结点当前结点就是公共结点 思路参考236. 二叉树的最近公共祖先 - 力扣Leetcode 小知识一般涉及到树的算法都是用递归来实现的。 3.代码实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null || root p || root q) {//只要当前根节点是p和q中的任意一个就返回因为不能比这个更深了再深p和q中的一个就没了return root;}//根节点不是p和q中的任意一个那么就继续分别往左子树和右子树找p和qTreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);//p和q都没找到那就没有返回nullif(left null right null) {return null;}//如果左子树没有p也没有q就返回右子树的结果if (left null) {return right;}//如果右子树没有p也没有q就返回左子树的结果if (right null) {return left;}//左右子树都找到p和q了那就说明p和q分别在左右两个子树上所以此时的最近公共祖先就是rootreturn root;}
}
