257 Binary Tree Paths

257. Binary Tree Paths
1. Question
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
   1
2
 /   \
3
2     3
4
 \
5
  5
Copied!
All root-to-leaf paths are:
1
["1->2->5", "1->3"]
Copied!
2. Implementation
(1) DFS
1
class Solution {
2
    public List<String> binaryTreePaths(TreeNode root) {
3
        List<String> res = new ArrayList<>();        
4
        getTreePaths(root, "", res);
5
        return res;
6
    }
7
​
8
    public void getTreePaths(TreeNode node, String curPath, List<String> res) {
9
        if (node == null) {
10
            return;
11
        }
12
​
13
        if (node.left == null && node.right == null) {
14
            res.add(curPath + node.val);
15
            return;
16
        }
17
​
18
        getTreePaths(node.left, curPath + node.val + "->", res);
19
        getTreePaths(node.right, curPath + node.val + "->", res);
20
    }
21
}
Copied!
(2) BFS
1
class Solution {
2
    public List<String> binaryTreePaths(TreeNode root) {
3
        List<String> res = new ArrayList<>();
4
        if (root == null) {
5
            return res;
6
        }
7
​
8
        Queue<TreeNode> queue = new LinkedList<>();
9
        Queue<String> path = new LinkedList<>();
10
​
11
        queue.add(root);
12
        path.add("");
13
​
14
        while (!queue.isEmpty()) {
15
            int size = queue.size();
16
​
17
            for (int i = 0; i < size; i++) {
18
                TreeNode curNode = queue.remove();
19
                String curPath = path.remove();
20
​
21
                if (curNode.left == null && curNode.right == null) {
22
                    res.add(curPath + curNode.val);
23
                }
24
​
25
                if (curNode.left != null) {
26
                    queue.add(curNode.left);
27
                    path.add(curPath + curNode.val + "->");
28
                }
29
​
30
                if (curNode.right != null) {
31
                    queue.add(curNode.right);
32
                    path.add(curPath + curNode.val + "->");
33
                }
34
            }
35
        }
36
        return res;
37
    }
38
}
Copied!
3. Time & Space Complexity
(1) DFS: 时间复杂度: O(n), 空间复杂度: O(h)
(2) BFS: 时间复杂度: O(n), 空间复杂度: O(w)

366 Find Leaves of Binary Tree

235 Lowest Common Ancestor of a Binary Search Tree

Last modified 2yr ago

Copy link

Contents

257. Binary Tree Paths

1. Question

2. Implementation

3. Time & Space Complexity