An O(N) recursive JAVA solution with comments (also attempts to explain how to read the input)


  • 2
    L

    I don't know why no one was trying to explain the input here. Maybe I've been too rusty about my data structure, and this is the default representation of BST nodes as an array.

    You can also checkout StefanPochmann's deserializer and visualizer, which is very useful.

    The input reads like this for [5, 3, 6, 2, 4, null, null, 1]:

               5
             /   \
            3     6
           / \    / \
          2   4  N   N
         /
        1
    

    where N is null.

    Basically you go from top level to bottom, then left to right within the level, but it took me a few minutes before I figured out how it is represented. (I couldn't even find a question related about this, so I assume most people remember it from how they used to do it.)

    Anyways, Here's my answer:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode smallerNode;
            TreeNode largerNode;
    
            if(p.val < q.val) {
                smallerNode = p;
                largerNode = q;
            } else {
                smallerNode = q;
                largerNode = p;
            }
            
            // if one is on your left, another on your right
            // or if one is yourself, and the other on either side
            // then the current root is the LCA
            if( smallerNode.val <= root.val && largerNode.val >= root.val ) {
                return root;
            } else if (largerNode.val < root.val) { //decide which way to go..
                return lowestCommonAncestor(root.left, smallerNode, largerNode);
            } else {
                return lowestCommonAncestor(root.right, smallerNode, largerNode);
            }
        }
    }
    

    I later found duplicated as https://leetcode.com/discuss/50436/my-java-recursive-solution


  • 0

    I don't know whether it's a standard tree representation outside of LeetCode, but at LeetCode it is. Some problems include a description, some don't. I wrote a deserializer and visualizer for it recently.

    Your solution btw isn't O(logN) but O(N), as the tree isn't necessarily balanced.


  • 0
    L

    Thanks for the useful visualizer :) Hope this will be another entry point to your awesome visualizer.
    I have also updated the title accordingly, thanks for pointing that out.


Log in to reply
 

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