If the tree is not binary search tree (BST), How to do ?


  • 0

    Yes, when looking at this problem, I was careless and didn't notice the tree is binary search tree. And I also solve this problem, so I want to share with you.

    The following is my ideas and code :
    traversal the tree

    • 1) if find two p and q, return 2
    • 2) if find one of p and q, return 1 and then rollback to the parent node, the common node also rollback to the parent node
    • 3) if find nothing of p or q, return 0 and do nothing to common node.
    private TreeNode common = null;
    
        /**
         * 
         * 27 / 27 test cases passed.
         * Status: Accepted
         * Runtime: 9 - 10ms, bit 26.45% - 14.05%
         *
         * @param root
         * @param p
         * @param q
         * @return
         */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            helper(root, p, q);
            return common;
        }
    
        /**
         * @param root
         * @param p
         * @param q
         * @return
         */
        private int helper(TreeNode root, TreeNode p, TreeNode q) {
            int count = 0;
            if (root == null) return count;
            if (root.val == p.val || root.val == q.val) {
                if (common == null) {
                    common = root;
                    count = 1;
                } else return 2;
            }
            int res = helper(root.left, p, q);
            if (res == 1) common = root;
            else if (res == 2) return res;
    
            return count + res + helper(root.right, p, q);
        }
    

  • 0

    I did the same mistake. This is my stupid passed solution.

    27 / 27 test cases passed.
    Status: Accepted
    Runtime: 9 ms
    Your runtime beats 26.49% of java submissions.
    
    public class Q235LowestCommonAncestorofaBinarySearchTree {
        TreeNode commonAncestor = null;
        public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        	//if this is null, means end of tree
        	if(root == null) return null;
        	TreeNode leftResult = lowestCommonAncestor2(root.left, p, q);
        	TreeNode rightResult = lowestCommonAncestor2(root.right, p, q);
        	//before every check, first check if the commonAncestor has found
        	if(commonAncestor != null) return commonAncestor;
        	
        	//two nodes come to one common ancestor
        	//if the left leave and right leave are not null, this node is the first common ancestor
        	if((leftResult != null) && (rightResult != null)){
        		commonAncestor = root;
        		return root;
        	}
        	//if one of the leafs is not null
        	else if(leftResult != null || (rightResult != null)){
        		//check current root, if it is one of two nodes, this is the first common ancestor
        		if((root.val == p.val) || (root.val == q.val)){
                		commonAncestor = root;
            	}
        		//if the current root is not the one, return the one that is not null to parent
        		return leftResult != null ? leftResult : rightResult ;
        	}
        	else {
        		//if both leafs are null, check current root
        		//if it belongs to the two nodes, return this root
        		if((root.val == p.val) || (root.val == q.val)){
        			return root;
        		}
        		//or no result in this subtree, return null
        		return null;
        	}
        }
    }
    

Log in to reply
 

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