在本文中，我们将详细介绍235.LowestCommonAncestorofaBinarySearchTree的各个方面，同时，我们也将为您带来关于#Leetcode#235.LowestCommon
在本文中，我们将详细介绍235. 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、236. Lowest Common Ancestor of a Binary Tree、236. Lowest Common Ancestor of a Binary Tree - Medium的有用知识。
本文目录一览：- 235. 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
- 236. Lowest Common Ancestor of a Binary Tree
- 236. Lowest Common Ancestor of a Binary Tree - Medium
235. Lowest Common Ancestor of a Binary Search Tree
/** * 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) { if (p->val > q->val) return lowestCommonAncestor(root,q,p); while (root != p && root != q) { if (p->val < root->val && q->val > root->val) return root; else if (p->val > root->val) root = root->right; else root = root->left; } 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 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,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, 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 binary tree.
难度：medium
题目：给定一二叉树，找出给定的两个结点的最低层的共同祖先结点。
根据LCA维基百科定义，最低公共祖先定义为两个节点p和q之间的最低公共祖先，它是T中同时具有p和q作为子代的最低节点(我们允许一个节点作为自身的子代)
思路：递归，后续遍历。
Runtime: 5 ms, faster than 100.00% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 33.9 MB, less than 69.83% of Java online submissions for Lowest Common Ancestor of a Binary 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 == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left == null ? right : right == null ? left : root;
}
}
236. Lowest Common Ancestor of a Binary Tree - Medium
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]
Example 1:
Input: root = [3,4],p = 5,q = 1 Output: 3 Explanation: The LCA 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 de@R_301_4319@n. 545
Note:
- All of the nodes‘ values will be unique.
- p and q are different and both values will exist in the binary tree.
M1: recursion
recursion + divide and conquer (左右两边分别递归）
base case: root为空，或者root为p或q
time: O(n),space: O(n) n: # nodes (worst case)
/** * De@R_301_4319@n 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) return root; if(root == p || root == q) return root; TreeNode leftnode = lowestCommonAncestor(root.left,p,q); TreeNode rightnode = lowestCommonAncestor(root.right,q); if(leftnode != null && rightnode != null) return root; else if(rightnode == null) return leftnode; else if(leftnode == null) return rightnode; else return null; } }
M2: iteration
今天的关于235. 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、236. Lowest Common Ancestor of a Binary Tree、236. Lowest Common Ancestor of a Binary Tree - Medium的相关知识，请在本站进行查询。
本文标签：
