Java Recursive Explained


  • 0

    Solution

    • Simple tree traversal recursively and returning list of paths from left and right sub tree
    • Append after current node value to make paths from current node to all leaf nodes in that sub tree
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            
            List<String> paths = new ArrayList<>();
            
            // if root is null return empty list;
            if (root == null) {
                return paths;
            }
            
            // if this is leaf node; retun paths with just this node;
            if (root.left == null && root.right == null) {
                paths.add(String.valueOf(root.val));
            } else {            
                // if left child is not null, get paths from left chile and append with root.value to make new paths from this node;
                if (root.left != null) {
                    List<String> leftPaths = binaryTreePaths(root.left);  
                    for (String path : leftPaths) {
                        paths.add(String.valueOf(root.val) + "->" + path);
                    }
                } 
                
                // if right child is not null, get paths from right child and append with root.val to make new paths from this node;
                if (root.right != null){
                    List<String> rightPaths = binaryTreePaths(root.right);
                    for (String path : rightPaths) {
                        paths.add(String.valueOf(root.val) + "->" + path);
                    }  
                } 
            }
            
            return paths;        
        }
    }
    

Log in to reply
 

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