Share some extension: LCA of k nodes in a BST or binary tree


  • 1
    T

    original question 1: LCA of 2 nodes in a BST.

    solution 1:

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == null || q == null)
                return null;
            
            TreeNode result = root; 
            int l = min(p.val, q.val);
            int r = max(p.val, q.val);
            while (!(l <= result.val && result.val <= r))
                if (result.val < l)
                    result = result.right;
                else
                    result = result.left;
            return result;
        }
        int min(int a, int b){
            return a < b? a: b;
        }
        int max(int a, int b){
            return a > b? a: b;
        }
    }
    

    extension question 2: to find LCA of two node in binary tree, e.g., not binary search tree.

    solution 2:

    public class Solution {
        TreeNode result = null;
        boolean findp = false;
        boolean findq = false;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root, p, q);
            return result;
        }
        int dfs(TreeNode root, TreeNode p, TreeNode q){
            if (root == null || (findp && findq))
                return 0;
                
            int cur = 0;
            if (root == p){
                cur += 2;
                findp = true;
            }
            if (root == q){
                cur +=1;
                findq = true;
            }
               
            int left = dfs(root.left, p, q);
            int right = dfs(root.right, p, q);
    
            if (cur + left + right == 3 && result == null)
                result = root;
            return cur + left + right;
        }
    }
    

    extension question 3: LCA of k nodes in BST.

    solution 3: only need to find max and min of k nodes and then to chang root into root.left or root.right according to the relationship of root.val and [min, max]. if root.val < min, let root = root.right; if root.val > max, let root = root.left; else this root is the answer. The complexity of time is O(k + logn) generally, and O(n) worst, and space is O(logn) generally, and O(n) worst.

    extension question 4: LCA of k nodes in binary tree(with the assumption of nodes are diffrent from each other).

    solution 4.1: time O(n), space O(k + logn) to O(n);

        class Solution{
            HashSet<TreeNode> hash = new HashSet<TreeNode>();
            TreeNode result = null;        
            TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes, int k)
            {
                for (node: nodes)
                    hash.put(node);
                dfs(root, nodes, k);
                return result;
            }
            int dfs(TreeNode root, int k){
                if (root == null || result != null)
                    return 0;
                
                int cur = hash.containsKey(root)? 1: 0;
                int l = dfs(root.left);
                int r = dfs(root.right);
                if (cur + l + r == k && result == null)
                    result = root;
                return l + r + cur;
            }
        }
    

    solution 4.2: time O(n), space O(n), to convert the binary tree to BST, then to solve it. The conversion needs inorder traversal of the original binary tree and number assignment in new BST, thus it needs O(n) time and space.Because the solution of LCA of k nodes in BST need no more time and space than this transformation, the totle time and space is as above.

    solution 4.3: time O(n + klogk), space O(k + logn + klogn), getting huffman codings of the k nodes and then obtaining the longest common preffix of these huffman codings and then finding the TreeNode corresponding to the preffix in the binary tree.


Log in to reply
 

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