link ：https://leetcode.cn/problems/binary-tree-pruning/solution/c-by-xun-ge-v-9zt4/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . 

subject

Example

Ideas

Their thinking
Recursion can basically solve tree related problems , Because the tree itself can be constructed recursively
About this topic, all that do not contain... Need to be removed 1 The original binary tree of the subtree . For the whole tree , We need to remove nodes that are not 1 Subtree node of , This problem is divided into several sub problems -> That is, for each node , Remove not as 1 Left and right child nodes of

Then the subproblem of recursion at each step

• Both remove the left and right child nodes of the current node, not 1 The node of

Concrete realization
The official code is much better than what I wrote myself
My idea is to recursively traverse each node , At the same time, the principle of depth first search is adopted , First traverse the child nodes , Because each node needs to consider the same sub problem, it is not necessary to remove the left and right sub nodes of the current node 1 The node of , So we need to judge every node , Judge whether the left node and the right node are 0, by 0 Remove the corresponding child node

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int dfs(struct TreeNode * root)
{
    if(root == NULL)
    {
        return 0;
    }
    int left = 0;// Record the value of the left child node 
    left = dfs(root->left);// Traverse the left child node , When the left child node always exists, it will traverse the left child node first , All the way to the leaf node of the left node 
    if(left == 0)// by 0, remove 
    {
        free(root->left);
        root->left = NULL;
    }
    int right = 0;// Record the right child node 
    right = dfs(root->right);// Traverse the right child node 
    if(right == 0)
    {
        free(root->right);
        root->right = NULL;
    }
    int n = (left > right ? left : right);// Returns whether the left child node and the right child node exist 1
    return n > root->val ? n : root->val;
}
/*
*struct TreeNode* pruneTree(struct TreeNode* root)
struct TreeNode* pruneTree： Removed all that do not contain  1  The original binary tree of the subtree 
struct TreeNode* root: Head node 
 Return value ： Remove the new binary tree head node 
*/
struct TreeNode* pruneTree(struct TreeNode* root){
    int m = dfs(root);// The head node may also be 0, Also remove 
    if(m == 0)
    {
        return NULL;
    }
    return root;
}

Time and space complexity