打印从 Root 到每个叶子的所有路径

Question

对于每个节点都具有以下元组的树：（值，左节点，右节点）如何打印从根到每个叶子的所有可能的价值链？例如： (1,(2,(4,(7,None,None),None),(5, None, None)),(3,None,(6, None,None)))它应该代表以下树：预期结果是：[1,2,4,7][1,2,5][1,3,6]

Answer 1

似乎您正在尝试解决此问题：https : //leetcode.com/problems/binary-tree-paths/

在这里，您可以简单地开始使用 dfs 探索树并在树中向下存储值并维护从根到当前节点的所有值的向量。处理完该节点后，只需从该向量中删除当前节点处的值。当我们到达叶节点时，我们只需将向量中的值附加到我们的答案中。

这是在 cpp 中实现的代码供您参考：

/**

* Definition for a binary tree node.

* struct TreeNode {

*     int val;

*     TreeNode *left;

*     TreeNode *right;

*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

 public:

   void solve(TreeNode* root, vector<int>&values, vector<string>&ans) {

    if (root == NULL) return;

    if (root->left == NULL && root->right == NULL) {

        // leaf node

        string str = "";

        values.push_back(root->val);

        str += ::to_string(values[0]);

        for (int i = 1; i < values.size(); ++i) {

            str += "->";

            str += ::to_string(values[i]);

        }

        ans.push_back(str);

        values.pop_back();

        return;

    }

    values.push_back(root->val);

    solve(root->left, values, ans);

    solve(root->right, values, ans);

    values.pop_back();

  }

 vector<string> binaryTreePaths(TreeNode* root) {

    vector<int>values;

    vector<string>ans;

    solve(root,values,ans);

    return ans;

  }

};