SHARE
TWEET

lowest common ancestor bst

a guest Oct 21st, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * map.contains
  9.  */
  10. class Solution {
  11.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  12.         //map to hold parent-child relationships and be able to backtrack
  13.         Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
  14.         //stack for traversing the tree, pushing children and popping in a while loop
  15.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  16.        
  17.         //put the initial values
  18.         map.put(root, null);
  19.         stack.push(root);
  20.        
  21.         //fill out the map with all nodes until it has both p and q
  22.         while (!map.containsKey(p) || !map.containsKey(q)){
  23.             if (!stack.isEmpty()){
  24.                 TreeNode node = stack.pop();
  25.                 if (node.left != null){
  26.                     map.put(node.left, node);
  27.                     stack.push(node.left);
  28.                 }
  29.                 if (node.right != null){
  30.                     map.put(node.right, node);
  31.                     stack.push(node.right);
  32.                 }
  33.             }
  34.         }
  35.        
  36.         //map now has all nodes up to p and q, now lets filter them out
  37.         //set to hold unique parents of P as we backtrack on the map
  38.         Set<TreeNode> pParents = new HashSet<TreeNode>();
  39.         //node to hold p's highest parent (null, since the root's parent is null)
  40.         TreeNode pParent = map.get(p);
  41.         pParents.add(p);
  42.         while (pParent != null){
  43.             pParents.add(pParent);
  44.             pParent = map.get(pParent);
  45.         }
  46.        
  47.         //now that we have all of p's parents in a set, lets return the first parent of q
  48.         //that appears in that set (thus, getting the lowest common ancestor)
  49.         TreeNode qParent = map.get(q);
  50.         while(!pParents.contains(qParent)){
  51.             qParent = map.get(q);
  52.         }
  53.        
  54.         //since the while loop stopped, qParent is suddenly in the ancestors set of p
  55.         //so its the first occurance of a shared parent
  56.         return qParent;
  57.        
  58.     }
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top