Java 5ms solution with Stack & Pre-order Travel


  • 0
    L
    public List<String> binaryTreePaths(TreeNode root) {
            List<String> paths = new ArrayList<String>();
            if(root == null ) {
                return paths;
            }
    
            Stack<TreeNode> stack = new Stack<TreeNode>();
    
            preOrderTravel(root, stack, paths);
            return paths;
        }
    
        private void preOrderTravel(TreeNode node, Stack<TreeNode> stack, List<String> paths) {
            if (node != null) {
                //Pre-order travel
                stack.add(node);
                if(node.left == null && node.right == null) {
                    recordPath(stack, paths);
                } else {
                    preOrderTravel(node.left, stack, paths);
                    preOrderTravel(node.right, stack, paths);
                }
    
                //Remove the leave node from the stack.
                stack.pop();
            }
        }
    
        private void recordPath(Stack<TreeNode> stack, List<String> paths) {
            StringBuilder sb = new StringBuilder(stack.size() * 10);
            for(TreeNode node: stack) {
                sb.append(node.val).append("->");
            }
    
            //Remove the last "->"
            sb.setLength(sb.length() - 2);
            paths.add(sb.toString());
        }

Log in to reply
 

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