剑指offer专项突击版第16天

剑指 Offer II 047. 二叉树剪枝
简单的dfs深搜回溯来遍历树，比较直观的写法

class Solution {
    
public:
    bool dfs(TreeNode* &root) {
    
        if(root == nullptr) return true;
        bool flag1 = dfs(root->left);
        bool flag2 = dfs(root->right);
        if(flag1) root->left = nullptr;
        if(flag2) root->right = nullptr;
        if(root->val == 0 && flag1 && flag2)
            return true; 
        else 
            return false;
    }

    TreeNode* pruneTree(TreeNode* root) {
    
        if(dfs(root)) root = nullptr;
        return root;
    }
};

更简洁的写法

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

---

剑指 Offer II 048. 序列化与反序列化二叉树

方法一：通过dfs深度优先来遍历树，然后例如下图的树生成的字符串为：1,2,N,N,3,4,N,N,5,N,N,
然后按照规律去解码即可，其中N代表空结点。

class Codec {
    
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
    
        if(root == nullptr) return "N,";
        else {
    
            string node = to_string(root->val) + ',' 
                + serialize(root->left)
                + serialize(root->right);                
            return node;
        }
    }

    TreeNode* rdeserialize(queue<string> &que) {
    
        string str = que.front();
        que.pop();
        if(str == "N") return nullptr;
        else {
    
            TreeNode *root = new TreeNode(stoi(str));
            root->left = que.size()? rdeserialize(que): nullptr;
            root->right = que.size()? rdeserialize(que): nullptr;
            return root;
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
    
        queue<string> que;
        string tmp;
        for(char c: data) {
    
            if(c == ',') {
    
                que.emplace(tmp);
                tmp.clear();
            } else {
    
                tmp.push_back(c);
            }
        }

        if(que.size()) return rdeserialize(que);
        else return nullptr;
    }

};

方法二：括号表示编码 + 递归下降解码
链接：https://leetcode.cn/problems/h54YBf/solution/xu-lie-hua-yu-fan-xu-lie-hua-er-cha-shu-dh5vl/

---

剑指 Offer II 049. 从根节点到叶节点的路径数字之和

本质上是求根节点到叶子结点路径上结点的序列。

class Solution {
    
public:
    int get_sum(TreeNode* root, int val) {
    
        if(!root->left && !root->right) //叶子结点 
			return val * 10 + root->val;
        int sum = 0;
        if(root->left) sum += get_sum(root->left, val * 10 + root->val);
        if(root->right) sum += get_sum(root->right, val * 10 + root->val);
        return sum;
    }

    int sumNumbers(TreeNode* root) {
    
        return get_sum(root,0);
    }
};