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

480-二叉树的所有路径

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

思路

使用深度优先搜索 + 回溯

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();

        }

    }

};