首页 > 代码库 > LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)
LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)
Lowest Common Ancestor of a Binary Search Tree
一、题目描写叙述
二、思路及代码
二叉搜索树有个性质:左子树的值都比根节点小,右子树的值比根节点大。那么我们的思路就是递归比較。
假设输入的两个节点的值比当前节点小,说明是在当前根节点的左子树中;反之则在右子树中。
假设当前根节点比一个大。比一个小。那么第一个出现的这种节点就是近期的父亲节点了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
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;
}
}
}
Lowest Common Ancestor of a Binary Tree
一、题目描写叙述
二、思路及代码
假设是普通的二叉树。没有了二叉搜索树的特性。就要遍历;于是我们用到DFS遍历树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root; //找到p或者q节点,或者到最底层的叶子节点时,返回;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root; //找到了父节点
return left != null ? left : right; //所以假设都未找到,返回null
}
}
LeetCode_Lowest Common Ancestor of a Binary Search Tree (Binary Tree)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。