Java iterative solution using DFS without additional space for level


  • 0
    W

    simple DFS algorithm. Every time, we only keep exact one path in the stack.

    public class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int depth = 0;
        
        Stack<TreeNode> st = new Stack<TreeNode>();
        
        TreeNode pre = null;
        
        TreeNode current = root;
        while(current!=null){
            st.push(current);
            current=current.left;
        }
        depth = Math.max(depth,st.size());
        while(!st.isEmpty()){
            TreeNode temp = st.peek();
            if(( temp.right==null) || (pre !=null && pre==temp.right)){
                pre = st.pop();
            }
            else{
                temp = temp.right;
                while(temp!=null){
                    st.push(temp);
                    temp=temp.left;
                }
            }
            depth = Math.max(depth,st.size());
        }
        return depth;
    }
    }

Log in to reply
 

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