html5 微信网站 源码,江宁区住房建设局网站,石家庄正定网站建设,wordpress手机端源码文章目录思路 代码代码 思路二刷思路 代码
应该在二叉树的最近公共祖先之前写 需要用到二叉搜索树的特性#xff5e;
代码 思路
分成四种情况即可#xff0c;具体见代码注释时间复杂度 O(logn)
/*** Definition for a binary tree node.* publ…
文章目录思路 代码代码 思路二刷思路 代码
应该在二叉树的最近公共祖先之前写 需要用到二叉搜索树的特性
代码 思路
分成四种情况即可具体见代码注释时间复杂度 O(logn)
/*** 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) {// 1. 为p | q的情况if(root p || root q){return root;}// 2. p q 都小于 root转换在左子树找if(p.val root.val q.val root.val){return lowestCommonAncestor(root.left, p, q);}// 3. 都大于转换右子树找if(p.val root.val q.val root.val){return lowestCommonAncestor(root.right, p, q);}// 4. 一个大一个小root 就是答案return root;}
}来个清晰版本的代码
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root p || root q){return root;}if(p.val root.val q.val root.val){return lowestCommonAncestor(root.left, p, q);}if(p.val root.val q.val root.val){return lowestCommonAncestor(root.right, p, q);}return root;}
}二刷
注意与二叉树的最近公共祖先不同这里可以利用二叉搜索树的性质当然用二叉树来的方法也可以。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root p || root q) {return root;}if(p.val root.val q.val root.val) {return lowestCommonAncestor(root.left, p, q);}else if(p.val root.val q.val root.val) {return lowestCommonAncestor(root.right, p, q);}return root;}
}
