首页 > itarticle > [leetcode] lc257

[leetcode] lc257

admin 11月 14, 2020 0

Description

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

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   
2     3
 
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

> Solve problem here

Thoughts

DFS recursive (top-down)

The most straight forward way to solve this problen is via recursive DFS.


public List<String> (TreeNode root) {
    // write your code here
    List<String> res = new ArrayList<>();
    helper(root, res, "");
    return res;
}
    
public void helper(TreeNode node, List<String> res, String s) {
    if (node == null) return;
    if (node.left == null && node.right == null) {
        res.add(new String(s + node.val));
        return;
    }
    
    // prep new string
    String newStr = new String(s + node.val + "->");
    
    // left & right
    helper(node.left, res, newStr);
    helper(node.right, res, newStr);
}

Add all nodes’s value along the way (top-down) and add path string into List<String> solution at leaf node.

DFS recursive (bottom-up)

The bottom up recursive approach is bit harder to come up with. I was not able to come up with it at first place.

ref: https://leetcode.com/problems/binary-tree-paths/discuss/68282/Clean-Java-solution-(Accepted)-without-any-helper-recursive-function

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new LinkedList<>(); // new List wo/ worry prev list, smart
    if(root == null) return paths;
    if(root.left == null && root.right == null){
        paths.add(root.val+"");
        return paths;
    }
     for (String path : binaryTreePaths(root.left)) {
         paths.add(root.val + "->" + path);
     }
     for (String path : binaryTreePaths(root.right)) {
         paths.add(root.val + "->" + path);
     }

     return paths;
}

DFS iterative (top-bottom)

DFS iterative approach can pre-order traversal, which is a top-down approach. The bottom-up appraoch is simliar w/ in-order traversal (bottom-up) but not implemented, below is the DFS iterative top-down via pre-order traversal.

// dfs iterative + preorder (top-down)
public List<String> (TreeNode root) {
    List<String> res = new ArrayList<>();
    
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    Deque<String> paths = new ArrayDeque<>();
    stack.push(root);
    paths.push(""); // key
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        String path = paths.pop();
        if (node.left == null && node.right == null) {
            res.add(path + node.val);   
        }
        if (node.right != null) {
            stack.push(node.right);
            paths.push(path + node.val + "->");
        }
        if (node.left != null) {
            stack.push(node.left);
            paths.push(path + node.val + "->"); 
        }
    }
    
    return res;
}

BFS iterative

// bfs iterative + leverl order
public List<String> (TreeNode root) {
    List<String> res = new ArrayList<>();
    if (root == null) return res;
    
    Deque<TreeNode> queue = new ArrayDeque<>();
    Deque<String> paths = new ArrayDeque<>();
    queue.offer(root);
    paths.offer(""); // key
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        String path = paths.poll();
        if (node.left == null && node.right == null) {
            res.add(path + node.val);   
        }

        if (node.left != null) {
            queue.offer(node.left);
            paths.offer(path + node.val + "->"); 
        }

        if (node.right != null) {
            queue.offer(node.right);
            paths.offer(path + node.val + "->");
        }
    }
    
    return res;
}

Summary

DFS recursive (bottom-up)
DFS recursive (top-down)
DFS iterative (top-down, pre-order traversal)
DFS iterative (bottom-up, in-order traversal)
BFS iterative
BFS iterative is similiar to DFS iterative (top-down, preorder)

Logs

02/04/19: solution added
TODO: dfs recursive/iterative bottom-up

Reference

https://leetcode.com/problems/binary-tree-paths/discuss/68282/Clean-Java-solution-(Accepted)-without-any-helper-recursive-function