首页 > 其他 > 详细

leetcode-back-257. 二叉树的所有路径

时间:2021-08-13 17:36:28      阅读:25      评论:0      收藏:0      [点我收藏+]

 

技术分享图片

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> res;
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==NULL)
            return res;
        string temp ="";

        back(root,temp);
        return res;
    }

    void back(TreeNode* root, string &temp){
         if(root==NULL)  // 空节点,不是叶节点
            return;
        string temp1 = to_string(root->val);
        string val = temp1.append("->");
        temp.append(val);
       
        if(root->left==NULL&&root->right==NULL){  // 此节点不空,左右子树为空,才为叶节点
            temp = temp.substr(0,temp.size()-2);  // 去除最后的->
            res.push_back(temp);
            temp = temp.substr(0,temp.size()-to_string(root->val).size()); // 回溯
            return;
        }
  
        back(root->left, temp);
        back(root->right, temp);

        temp = temp.substr(0,temp.size()-val.size());  // 回溯
       
    }
};

可以看到上面的这种解法是因为对temp加了引用,如果不加引用,则可以不用回溯,但是有超时的风险,此题没有超时,不加引用本质上是空间换时间

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> res;
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==NULL)
            return res;
        string temp ="";

        back(root,temp);
        return res;
    }

    void back(TreeNode* root, string &temp){
         if(root==NULL)  // 空节点,不是叶节点
            return;
        string temp1 = to_string(root->val);
        string val = temp1.append("->");
        temp.append(val);
       
        if(root->left==NULL&&root->right==NULL){  // 此节点不空,左右子树为空,才为叶节点
            temp = temp.substr(0,temp.size()-2);  // 去除最后的->
            res.push_back(temp);
           // temp = temp.substr(0,temp.size()-to_string(root->val).size()); // 回溯
            return;
        }
  
        back(root->left, temp);
        back(root->right, temp);

       // temp = temp.substr(0,temp.size()-val.size());  // 回溯
       
    }
};

 

leetcode-back-257. 二叉树的所有路径

原文:https://www.cnblogs.com/ymec/p/15136994.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!