257. Binary Tree Paths

Description

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, 2, 3, null, 5]

Output: ["1->2->5", "1->3"]

Example 2

Input: [1, 2, 3, null, 5, 6, 7, 8, 9]

Output: ["1->2->5->8", "1->2->5->9", "1->3->6", "1->3->7"]

Example 3

Input: [1]

Output: ["1"]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { 
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    private List<String> resultList;
    
    public List<String> binaryTreePaths(TreeNode root) {
        resultList = new ArrayList();
        constructPath(root, new StringBuilder());
        return resultList;
    }
    
    private void constructPath(TreeNode node, StringBuilder path) {
        if(node == null) {
            return;
        }
        int len = path.length();
        
        path.append(node.val);
        if(node.left == null && node.right == null) {
            resultList.add(path.toString());
        } else {
            path.append("->");
        }
        
        constructPath(node.left, path);
        constructPath(node.right, path);
        path.setLength(len);
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */
 
 class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> resultList = new ArrayList();
        if(root == null) {
            return resultList;
        }
        Stack<TreeNode> nodeStack = new Stack();
        Stack<String> pathStack = new Stack();
        nodeStack.push(root);
        pathStack.push(Integer.toString(root.val));
        
        while(!nodeStack.isEmpty()) {
            TreeNode curr = nodeStack.pop();
            String path = pathStack.pop();
            if(curr.left == null && curr.right == null) {
                resultList.add(path);
            }
            if(curr.left != null) {
                nodeStack.push(curr.left);
                pathStack.push(path + "->" + Integer.toString(curr.left.val));
            }
            if(curr.right != null) {
                nodeStack.push(curr.right);
                pathStack.push(path + "->" + Integer.toString(curr.right.val));
            }
        }
        return resultList;
    }
}

Follow up