如果您对LowestCommonAncestorofaBinarySearchTree感兴趣，那么这篇文章一定是您不可错过的。我们将详细讲解LowestCommonAncestorofaBinaryS
如果您对Lowest Common Ancestor of a Binary Search Tree感兴趣，那么这篇文章一定是您不可错过的。我们将详细讲解Lowest Common Ancestor of a Binary Search Tree的各种细节，此外还有关于#Leetcode# 235. Lowest Common Ancestor of a Binary Search Tree、235. Lowest Common Ancestor of a Binary Search Tree、235.Lowest Common Ancestor of a Binary Search Tree、236. Lowest Common Ancestor of a Binary Tree的实用技巧。
本文目录一览：- Lowest Common Ancestor of a Binary Search Tree
- #Leetcode# 235. Lowest Common Ancestor of a Binary Search Tree
- 235. Lowest Common Ancestor of a Binary Search Tree
- 235.Lowest Common Ancestor of a Binary Search Tree
- 236. Lowest Common Ancestor of a Binary Tree
Lowest Common Ancestor of a Binary Search Tree
问题：
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
解决：
① 如果如果p,q 比root小, 则LCA必定在左子树, 如果p,q比root大, 则LCA必定在右子树. 如果一大一小, 则root即为LCA.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution { // 9ms
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null) return null;
if(Math.max(p.val,q.val) < root.val) return lowestCommonAncestor(root.left,p,q);
else if(Math.min(p.val,q.val) > root.val) return lowestCommonAncestor(root.right,p,q);
else return root;
}
}
② 一个细节
public class Solution { //8ms
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null) return null;
if(Math.max(p.val,q.val) < root.val) return lowestCommonAncestor(root.left,p,q);
if(Math.min(p.val,q.val) > root.val) return lowestCommonAncestor(root.right,p,q);
return root;
}
}
#Leetcode# 235. Lowest Common Ancestor of a Binary Search Tree
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
Given a binary search tree (BST),find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,4,7,9,null,3,5]
Example 1:
Input: root = [6,5],p = 2,q = 8 Output: 6 Explanation: The LCA of nodes and is . 286
Example 2:
Input: root = [6,q = 4 Output: 2 Explanation: The LCA of nodes and is,since a node can be a descendant of itself according to the LCA deFinition. 242
Note:
- All of the nodes‘ values will be unique.
- p and q are different and both values will exist in the BST.
代码：
/**
* DeFinition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x),left(NULL),right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q) {
int v1 = p -> val;
int v2 = q -> val;
int r = root -> val;
if(v1 > r && v2 < r || v1 < r && v2 > r)
return root;
if(v1 == r || v2 == r)
return root;
if(v1 < r)
return lowestCommonAncestor(root -> left,p,q);
else
return lowestCommonAncestor(root -> right,q);
}
};
感觉好多递归哦
235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
找二叉搜索树中两个节点的最小公共父节点。父节点可以包括自身。
因为是二叉搜索树，使得搜索子节点的路径只剩下一条。
1、两个都大于 root，找 root->right;
2、两个都小于 root，找 root->left;
3、不符合 1,2，就返回 root。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root)
return root;
int low = min(p->val, q->val);
int high = max(p->val, q->val);
int rt = root->val;
if (high < rt)
return lowestCommonAncestor(root->left, p, q);
else if (low > rt)
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};
235.Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST),find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the deFinition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,4,7,9,null,3,5]
_______6______
/ ___2__ ___8__
/ \ / 0 _4 7 9
/ 3 5
Example 1:
Input: root = [6,5],p = 2,q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2,since a node can be a descendant of itself
according to the LCA deFinition.
Note:
- All of the nodes‘ values will be unique.
- p and q are different and both values will exist in the BST.
# DeFinition for a binary tree node.
class TreeNode:
def __init__(self,x):
self.val = x
self.left = None
self.right = None
class Solution:
def lowestCommonAncestor(self,root,p,q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root:
return None
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left,q) #这里需要return，因为不需要回溯，找到就可以了
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right,q)
else:
return root
236. Lowest Common Ancestor of a Binary Tree
问题描述：
Given a binary tree,find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,8,null,7,4]
_______3______
/ ___5__ ___1__
/ \ / 6 _2 0 8
/ 7 4
Example 1:
Input: root = [3,4],p = 5,q = 1 Output: 3 Explanation: The LCA of of nodes and is 513.
Example 2:
Input: root = [3,q = 4
Output: 5
Explanation: The LCA of nodes and is,since a node can be a descendant of itself
according to the LCA deFinition.545
Note:
- All of the nodes‘ values will be unique.
- p and q are different and both values will exist in the binary tree.
解题思路：
找两个节点最低的祖先节点，并且一个节点可以成为它自己的祖先节点。
我们可以先找到其中一个节点，这个时候我们需要遍历树，我在这里采用的是使用栈的前序遍历，当该节点值等于目标节点其中一个的值时，跳出循环。
找到的点为findN，未找到的为targetN
这个时候我们可以考虑两个点之间的关系：
1. targetN是findN的子节点
2.targetN不是findN的子节点
所以我们首先需要搜寻findN的子树，若包含targetN，则直接返回findN
若不包含，则需要从栈内弹出一个节点并且搜寻它的子树。
这里我们可以进行剪枝，因为此时栈顶是我们findN的父节点，并且我们已经搜索过了findN的子树，我们就不需要搜索它的左子树了。
但是targetN很可能是findN的父节点， 所以我们先要对栈顶值进行检查，如果不是我们想要找的值，则检查它的右子树
代码：
/** * DeFinition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),left(NULL),right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q) { stack<TreeNode*> stk; int restNode = 2; TreeNode* cur = root; while(cur || !stk.empty()){ if(cur){ if(cur->val == p->val || cur->val == q->val){ break; } stk.push(cur); cur = cur->left; }else{ cur = stk.top(); stk.pop(); cur = cur->right; } } TreeNode* targetN = cur->val == p->val ? q : p; TreeNode* findN = cur; if(containsNode(cur,targetN)){ return cur; } while(!stk.empty()){ cur = stk.top(); if(cur->val == targetN->val) break; stk.pop(); if(containsNode(cur->right,targetN)) break; } return cur; } bool containsNode(TreeNode* root,TreeNode* t){ if(!root) return false; stack<TreeNode*> stk; TreeNode* cur = root; while(cur || !stk.empty()){ if(cur){ if(cur->val == t->val) return true; stk.push(cur); cur = cur->left; }else{ cur = stk.top(); stk.pop(); cur = cur->right; } } return false; } };
今天关于Lowest Common Ancestor of a Binary Search Tree的分享就到这里，希望大家有所收获，若想了解更多关于#Leetcode# 235. Lowest Common Ancestor of a Binary Search Tree、235. Lowest Common Ancestor of a Binary Search Tree、235.Lowest Common Ancestor of a Binary Search Tree、236. Lowest Common Ancestor of a Binary Tree等相关知识，可以在本站进行查询。
本文标签：
