Simple Iterative O(N) time, O(logn) space solution


  • 0
    R
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        Deque<TreeNode> dq = new LinkedList<TreeNode>();
        
        public int getMinimumDifference(TreeNode root) {
            boolean firstTime = false;
            int curr = 0;
            while(root!=null){
                dq.addFirst(root);
                curr = root.val;
                root = root.left;
            }
            
            int diff = Integer.MAX_VALUE;
            while(!dq.isEmpty()){
                TreeNode temp = dq.removeFirst();
                if(firstTime){
                    diff = Math.min((temp.val - curr),diff);
                    curr = temp.val;
                }
                else{
                    firstTime = true;
                 }
                if(temp.right!=null){
                    temp = temp.right;
                    while(temp!=null){
                        dq.addFirst(temp);
                        temp = temp.left;
                    }
                }
            }
            return diff;
        }
    }```

Log in to reply
 

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