lintcode-480-二叉树的所有路径

480-二叉树的所有路径

给一棵二叉树，找出从根节点到叶子节点的所有路径。

您在真实的面试中是否遇到过这个题？ Yes

样例

给出下面这棵二叉树：

所有根到叶子的路径为：

[

"1->2->5",

"1->3"

]

标签

二叉树 谷歌 二叉树遍历 脸书

思路

使用深度优先搜索 + 回溯

code

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
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
        if (root == NULL) {
            return vector<string>();
        }
        vector<string> result;
        vector<int> path;
        DFS(root, path, result);
        return result;
    }    void DFS(TreeNode * root, vector<int> &path, vector<string> &result) {
        path.push_back(root->val);
        if (root->left == NULL && root->right == NULL) {
            string temp;
            for (int p : path) {
                char pa[256];
                sprintf(pa, "%d", p);
                temp += pa;
                temp += "->";
            }
            result.push_back(temp.substr(0, temp.size()-2));
            return;
        }
        if (root->left != NULL) {
            DFS(root->left, path, result);
            path.pop_back();
        }
        if (root->right != NULL) {
            DFS(root->right, path, result);
            path.pop_back();
        }
    }
};