Java - Bottom Up Recursion - Simple. Prepending Root


  • 0
    D

    I wanted a clear base base. when Root is null, there is no path. The only special case we handle is when you are at a leaf node, your left and right children gave you no paths. So you start a path with just yourself.

    public class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            
            List<String> paths = new ArrayList<>();
            if (root == null) {
                return paths;
            } 
            
            List<String> leftRightPaths = binaryTreePaths(root.left);
            leftRightPaths.addAll(binaryTreePaths(root.right));
            
            // The list is not empty if we have pushed at least the leaf
            for (String p : leftRightPaths) {
                paths.add(Integer.toString(root.val) + "->" + p);
            }
            
            // This is really our secondary base case. We push the leaf. This depends on the nullity of the first base case.
            if (leftRightPaths.size() == 0) {
                paths.add(Integer.toString(root.val));
            }
            
            return paths;
        }
    

Log in to reply
 

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