[JAVA] Inorder traversal / T : O(N), S : O(logN)


  • 0
    J
    class Solution {
        public int getMinimumDifference(TreeNode root) {
            Stack<TreeNode> st = new Stack<TreeNode>();
            
            TreeNode cur = root;
            while(cur != null){
                st.push(cur);
                cur = cur.left;
            }
            
            int min = Integer.MAX_VALUE;
            boolean notfirst = false;
            int pre = 0; 
            while(!st.isEmpty()){
                cur = st.pop();
                TreeNode next = cur.right;
                while(next != null){
                    st.push(next);
                    next = next.left;
                }
                
                // Update min 
                if(notfirst){
                    if(cur.val - pre < min)
                        min = cur.val - pre;
                }
                else
                    notfirst = true;
                
                pre = cur.val;
            }
            
            return min;
        }
        
    }
    

Log in to reply
 

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