在这里，我们将给大家分享关于leetcode235.LowestCommonAncestorofaBinarySearchTree的知识，同时也会涉及到如何更有效地#Leetcode#235.Lowe

在这里，我们将给大家分享关于leetcode 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、235.Lowest Common Ancestor of a Binary Search Tree、236. Lowest Common Ancestor of a Binary Tree的内容。

• leetcode 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
• 235.Lowest Common Ancestor of a Binary Search Tree
• 236. Lowest Common Ancestor of a Binary Tree

leetcode 235. Lowest Common Ancestor of a Binary Search Tree

        _______6______
       /                  ___2__          ___8__
   /      \        /         0      _4       7       9
         /           3   5

Input: root,p = 2,q = 8
Output: 6 
Explanation: The LCA of nodes  and  is .
286

Input: root,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

# DeFinition for a binary tree node.
# class TreeNode(object):
#     def __init__(self,x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self,root,p,q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        node = root
        while node:
            if node.val in {p.val,q.val}:
                return node
            elif node.val > p.val and node.val > q.val:
                node = node.left
            elif node.val < p.val and node.val < q.val:
                node = node.right
            else:
                return node                                

#Leetcode# 235. Lowest Common Ancestor of a Binary Search Tree

Input: root = [6,5],p = 2,q = 8
Output: 6
Explanation: The LCA of nodes  and  is .
286

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

/**
 * 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   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.

找二叉搜索树中两个节点的最小公共父节点。父节点可以包括自身。

因为是二叉搜索树，使得搜索子节点的路径只剩下一条。

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

_______6______
       /                  ___2__          ___8__
   /      \        /         0      _4       7       9
         /           3   5

# 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 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).”

_______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left != null && right != null){
            return root;
        }
        
        if(left != null){
            return left;
        }else{
            return right;
        }
    }
}

// To find LCA of nodes n1 and n2 in Binary Tree
    Node LCA(Node n1, Node n2) 
    {
        // Creata a map to store ancestors of n1
        Map<Node, Boolean> ancestors = new HashMap<Node, Boolean>();
 
        // Insert n1 and all its ancestors in map
        while (n1 != null) 
        {
            ancestors.put(n2, Boolean.TRUE);
            n1 = n1.parent;
        }
 
        // Check if n2 or any of its ancestors is in
        // map.
        while (n2 != null) 
        {
            if (ancestors.containsKey(n2) != ancestors.isEmpty())
                return n2;
            n2 = n2.parent;
        }
 
        return null;
    }

Node lca(Node node, int n1, int n2) 
    {
        if (node == null)
            return null;
  
        // If both n1 and n2 are smaller than root, then LCA lies in left
        if (node.data > n1 && node.data > n2)
            return lca(node.left, n1, n2);
  
        // If both n1 and n2 are greater than root, then LCA lies in right
        if (node.data < n1 && node.data < n2) 
            return lca(node.right, n1, n2);
  
        return node;
    }

指向parent的指针的做法，不用额外空间的是这样的：

            1. 得到2个链条的长度。

2.将长的链条向前移动差值（len1 - len2）

3.两个指针一起前进，遇到相同的即是交点，如果没找到，返回null.

public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getLen(headA);
        int lenB = getLen(headB);
        
        if (lenA > lenB) {
            while (lenA > lenB) {
                headA = headA.next;
                lenA--;
            }
        } else {
            while (lenA < lenB) {
                headB = headB.next;
                lenB--;
            }
        }
        
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    
    public int getLen(ListNode node) {
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }
        return len;
    }

关于leetcode 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、235.Lowest Common Ancestor of a Binary Search Tree、236. Lowest Common Ancestor of a Binary Tree等相关知识的信息别忘了在本站进行查找喔。