想了好久自己没想出来,是因为昨天没睡好吗？这也能简单？？
和第113题path-sum-ii很像

官方回答两种办法

1.(递归) 这个递归，返回值为空，通过一直传递path就行了，反正我写不出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }

    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}

2.DFS(迭代)维护两个stack，进出操作一摸一样。反正很巧妙，说不清。。
时隔一年觉得可以说清了 为每个节点出栈时分配一个记录当前路径 空间换时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(root == NULL) return res;

        stack<TreeNode*> stack1;  // 存放遍历的结点
        stack<string> stack2;  // 存放从根节点到遍历结点的路径
        stack1.push(root);
        stack2.push(to_string(root->val)+ "");

        while(!stack1.empty()){
            // 结点和该结点的路径同时出栈
            TreeNode* node = stack1.top();  stack1.pop();
            string path = stack2.top();  stack2.pop();
            
            if(node->left == NULL && node->right == NULL) {
                res.push_back(path);
            }
            else {
                if(node->left) {
                    stack1.push(node->left);
                    stack2.push(path + "->" + to_string(node->left->val));
                }
                if(node->right) {
                    stack1.push(node->right);
                    stack2.push(path + "->" + to_string(node->right->val));
                }
            }
                
        }
        return res;
    }
};

3.BFS(迭代)
维护两个队列，进出操作一摸一样。反正很巧妙，说不清。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();

        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll(); 
            String path = pathQueue.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }

                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }
}