SHARE
TWEET

Untitled

a guest Sep 20th, 2019 106 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Runtime: 6 ms, faster than 68.68% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
  2. // Memory Usage: 35.8 MB, less than 5.55% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
  3. class Solution {
  4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  5.         LinkedList<TreeNode> pPath = new LinkedList<>();        
  6.         search(root, p, pPath);
  7.                
  8.         TreeNode last, parent;
  9.                
  10.         last = pPath.pollLast();
  11.         if (search2(last, q)) return last;
  12.        
  13.         for (;;) {
  14.             if (last == q) return last;
  15.            
  16.             parent = pPath.pollLast();
  17.             if (parent == q) return parent;
  18.             if (parent == null) break;
  19.            
  20.             TreeNode alt = (parent.left == last) ? parent.right: parent.left;
  21.             if (alt != null && search2(alt, q)) return parent;
  22.            
  23.             last = parent;
  24.         }
  25.        
  26.         return null;
  27.     }
  28.    
  29.     private boolean search(TreeNode root, TreeNode node, LinkedList<TreeNode> path) {
  30.         path.add(root);
  31.         if (root == node) {            
  32.             return true;
  33.         }
  34.         if (root.left != null && search(root.left, node, path)) {
  35.             return true;
  36.         }
  37.         if (root.right != null && search(root.right, node, path)) {
  38.             return true;
  39.         }
  40.         path.removeLast();
  41.         return false;
  42.     }
  43.    
  44.      private boolean search2(TreeNode root, TreeNode node) {        
  45.         if (root == node) {            
  46.             return true;
  47.         }
  48.         if (root.left != null && search2(root.left, node)) {
  49.             return true;
  50.         }
  51.         if (root.right != null && search2(root.right, node)) {
  52.             return true;
  53.         }        
  54.         return false;
  55.     }
  56. }
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