Binary Tree Paths

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

http://www.lintcode.com/en/problem/binary-tree-paths/

Discussion

递归的思路很简单，分治思想。

//O(n*h) run time. 
//O(n) space for sub-tree path, O(h) space for stack.
class Solution {
public:
    /**
     * @param root the root of the binary tree
     * @return all root-to-leaf paths
     */
    vector<string> binaryTreePaths(TreeNode* root) {
        // Write your code here
        vector<string> result;
        if(root == NULL) {
            return result;
        }
        vector<string> left = binaryTreePaths(root->left);
        vector<string> right = binaryTreePaths(root->right);
        string cur = to_string(root->val);
        if(left.empty() && right.empty()) {//刚开始忘记这里，如果是叶子节点，直接输出，返回
            result.push_back(cur);
            return result;
        }
        for(int i=0; i<left.size(); i++) {
            result.push_back(cur + "->" + left[i]);
        }
        for(int i=0; i<right.size(); i++) {
            result.push_back(cur + "->" + right[i]);
        }
        return result;
    }
};

Follow up

上述算法一个缺点就是要为每次的递归构建vector, time consuming. 下面是个DFS的写法。

//O(n*h) run time. 
//O(h) space for stack.
class Solution {
public:
    /**
     * @param root the root of the binary tree
     * @return all root-to-leaf paths
     */
    vector<string> binaryTreePaths(TreeNode* root) {
        // Write your code here
        vector<string> result;
        if(root == NULL) {
            return result;
        }
        vector<TreeNode*> nodes_list;
        nodes_list.push_back(root);
        dfs(root, nodes_list, result);
        return result;
    }
    //nodes: all the tree nodes in the current path
    //paths: output paths
    void dfs(TreeNode *root, vector<TreeNode *> &nodes, vector<string> &paths) {
        if(root == NULL) {
            return;
        }
        if(root->left == NULL && root->right == NULL) {
            string one_path = to_string(nodes[0]->val);
            for(int i=1; i<nodes.size(); i++) {
                one_path += "->" + to_string(nodes[i]->val);
            }
            paths.push_back(one_path);
        }
        if(root->left != NULL) {
            nodes.push_back(root->left);
            dfs(root->left, nodes, paths);
            nodes.pop_back();
        }
        if(root->right != NULL) {
            nodes.push_back(root->right);
            dfs(root->right, nodes, paths);
            nodes.pop_back();
        }
    }
};