General Java solution for all kinds of tree, not just the BST.


  • -1
    J
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ArrayList<TreeNode> parray = new ArrayList<TreeNode>();
        ArrayList<TreeNode> qarray = new ArrayList<TreeNode>();
        getAnc(root, p, parray, false);
        getAnc(root, q, qarray, false);
        HashSet<TreeNode> wtf = new HashSet<TreeNode>();
        for (TreeNode i:parray) wtf.add(i);
        for (TreeNode i:qarray) {
            if (wtf.contains(i)) return i;
        }
        return null;
    }
    
    public boolean getAnc(TreeNode root, TreeNode p, ArrayList<TreeNode> result, boolean record) {
    	if (root == null) return false;
    	record = getAnc(root.left, p, result, record) | getAnc(root.right, p, result, record);
    	if (root.val == p.val) record = true;
    	if (record) result.add(root);
    	return record;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.