[数据结构与算法]力扣剑指offer第17天 树

47）二叉树剪枝

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
      if(root->left) root->left = pruneTree(root->left);
      if(root->right) root->right = pruneTree(root->right);
      if(root->left==nullptr && root->right==nullptr && root->val == 0) return nullptr;
      return root;
    }
};

48）序列化与反序列化二叉树

class Codec {
public:
    TreeNode* next_node(stringstream& ss){
      string tmp;
      ss >> tmp;
      if(tmp[0] == 'x') return nullptr;
      else return new TreeNode(stoi(tmp));
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        auto cur = root;
        stack<TreeNode*> s;
        while(cur!=nullptr || !s.empty()){
          while(cur!=nullptr){
            res += to_string(cur->val);
            res.push_back(' ');
            s.push(cur);
            cur = cur->left;
          }
          res.push_back('x');
          res.push_back(' ');
          cur = s.top(); s.pop();
          cur = cur->right;
        }
        res.push_back('x');
        res.push_back(' ');
        cout << res << endl;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        TreeNode* root = next_node(ss);

        TreeNode* cur = root;
        stack<TreeNode*> s;
        while(cur!=nullptr || !s.empty()){
          while(cur!=nullptr){
            s.push(cur);
            cur = cur->left = next_node(ss);
          }
          cur = s.top(); s.pop();
          cur = cur->right = next_node(ss);
        }
      return root;
    }
};

49)从根节点到叶节点的路径数字之和

class Solution{
public:
    int sumNumbers(TreeNode* root){
        return dfs(root, 0);
    }
    int dfs(TreeNode* root, int presum){
        if(!root) return 0;
        int sum = presum*10 + root->val;
        if(root->left || root->right){
            return dfs(root->left, sum)+dfs(root->right, sum);
        }else return sum;
    }
};