Java Depth First Stack Implementation - Slow Run Time


  • 0
    S
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int maxDepth(TreeNode root) {
           Stack dfs = new Stack ();
           int max = 0 ; 
           // initialize the stack with the root node as long as its not empty
           if (root != null) 
           dfs.push(root); 
           else 
           return 0; 
           TreeNode temp = root; 
           // set current root to visited. 
           temp.val = 1; 
           // set everything to unvisited. 
           if (temp.right != null) temp.right.val = 0; 
            if (temp.left != null) temp.left.val = 0; 
           // first get a condition to stop the looop: stack is empty 
           while (dfs.empty() == false) {
              
              if (temp.right != null && 
                    temp.right.val != 1 ) {
                   temp.val = 1;
                  temp = temp.right ;
                   if (temp.right != null) temp.right.val = 0; 
                    if (temp.left != null) temp.left.val = 0; 
                  dfs.push(temp); 
              }
              else if (temp.left != null  && 
                    temp.left.val != 1) {
                  temp.val = 1; 
                  temp = temp.left; 
                   if (temp.right != null) temp.right.val = 0; 
                    if (temp.left != null) temp.left.val = 0; 
                  dfs.push(temp); 
              }
              else if (temp.right == null && temp.left == null ) {  // terminal node 
                  if (max < dfs.search(root) ) max = dfs.search(root); 
                  temp.val = 1; 
                  // pop from stack and now if the stack isn't empty 
                  dfs.pop(); 
                  // reassign the new pointer to the node at the top of the stack 
                  if (!dfs.empty()) temp = (TreeNode) dfs.peek(); else break; 
              }
              else {  // going back up the tree so , lets
                  temp.val = 1; 
                  dfs.pop(); 
                  if (!dfs.empty()) temp = (TreeNode) dfs.peek(); 
                  else break; 
              }
              
              
           }
           
           return max; 
        }
    }
    

Log in to reply
 

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