My Java recursive solution


  • 1
    Q
    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<List<Integer>> paths = new ArrayList<List<Integer>>();
            getPaths(root, new LinkedList<Integer>(), paths);
            List<String> result = new ArrayList<String>();
            StringBuilder b = new StringBuilder();
            for (List<Integer> path:paths){
                b.setLength(0);
                b.append(path.remove(0));
                for (int i:path){
                    b.append("->").append(i);
                }
                result.add(b.toString());
            }
            return result;
        }
        
        private void getPaths(TreeNode parent, List<Integer> path, List<List<Integer>> paths){
            if (parent!=null){
                path.add(parent.val);
                if (parent.left == null && parent.right == null){
                    paths.add(new LinkedList<Integer>(path));
                }
                getPaths(parent.left, path, paths);
                getPaths(parent.right, path, paths);
                path.remove(path.size()-1);
            }
        }
    }

  • 0
    Q
    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> result = new ArrayList<>();
            Stack<Integer> path = new Stack<Integer>();
            binaryTreePathsHelper(root, path, result);
            return result;
        }
        
        private void binaryTreePathsHelper(TreeNode root, Stack<Integer> path, List<String> result) {
            if (root == null)  return;
            path.push(root.val);
            if (root.left == null && root.right == null){
                // process result
                StringBuilder sb = new StringBuilder();
                for (Integer nd : path){
                    sb.append(nd);
                    sb.append("->");
                }
                result.add(sb.substring(0, sb.length() - 2));
            }
            binaryTreePathsHelper(root.left, path, result);
            binaryTreePathsHelper(root.right, path, result);
            path.pop(); // remove parent
        }
    }

Log in to reply
 

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