A clean non-recursive solution in Java


  • 0
    T

    Codes:

    public class Solution {
    private String printStack(TreeNode leaf, Map<TreeNode, TreeNode> parentMap) {

        String separator = "->";
        
        ArrayList<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode current = leaf;
        while (current != null) {
            path.add(current);
            
            current = parentMap.get(current);
        }
        StringBuilder builder = new StringBuilder();
        ListIterator<TreeNode> reverseIterator = path.listIterator(path.size());
        while (reverseIterator.hasPrevious()) {
            TreeNode node = reverseIterator.previous();
            
            builder.append(node.val);
            builder.append(separator);
        }
        
        return builder.substring(0, builder.length() - separator.length());
    }
    
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> result = new ArrayList<String>();
        if (root == null) {
            return result;
        }
        
        ArrayList<TreeNode> nodeStack = new ArrayList<TreeNode>();
        ArrayList<Boolean> booleanStack = new ArrayList<Boolean>();
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<TreeNode, TreeNode>();
        
        nodeStack.add(root);
        booleanStack.add(false);
        while (nodeStack.size() > 0) {
            TreeNode current = nodeStack.get(nodeStack.size() - 1);
            boolean visited = booleanStack.get(booleanStack.size() - 1);
            if (visited) {
                nodeStack.remove(nodeStack.size() - 1);
                booleanStack.remove(booleanStack.size() - 1);
            } else {
                booleanStack.set(booleanStack.size() - 1, true);
                boolean isLeaf = true;
                if (current.left != null) {
                    nodeStack.add(current.left);
                    booleanStack.add(false);
                    parentMap.put(current.left, current);
                    isLeaf = false;
                }
                
                if (current.right != null) {
                    nodeStack.add(current.right);
                    booleanStack.add(false);
                    parentMap.put(current.right, current);
                    isLeaf = false;
                }
                
                if (isLeaf) {
                    result.add(printStack(current, parentMap));
                }
            }
        }
        
        return result;
    }
    

    }


Log in to reply
 

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