Iterative Accepted Solution Java


  • 0
    R

    The idea is to have two stacks. One stack for node traversal and another stack to store the previous paths. The base condition is when you hit the leaf of the tree (node with left and right null) then add the paths to the list.

    List<String> totalPaths = new ArrayList<>();
            if(root == null){
                return totalPaths;
            }
            List<String> allPathsFromRoot = new ArrayList<>();
            Stack<TreeNode> nodeStack = new Stack<>();
            Stack<String> pathStack = new Stack<>();
            nodeStack.push(root);
            pathStack.push(root.val+"");
            while(!nodeStack.isEmpty()){
                TreeNode node = nodeStack.pop();
                String previousPath = pathStack.pop();
                if(node.right == null && node.left == null){
                    allPathsFromRoot.add(previousPath);
                    continue;
                }
                if(node.right != null) {
                    pathStack.push(previousPath+"->"+node.right.val);
                    nodeStack.push(node.right);
                }
                if(node.left != null){
                    pathStack.push(previousPath+"->"+node.left.val);
                    nodeStack.push(node.left);
                }
                
            }
            return allPathsFromRoot;
    

Log in to reply
 

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