剑指 Offer II 047. 二叉树剪枝

若把全为 0 的二叉树称为零树，那么判断一棵树为零树的的规则是，左右子树都为零树（或者空指针）且根节点的值为0。

因为二叉树结构的递归性质，所以可以用同样的规则判断左右子树是否为零树。

在使用递归函数时，让根节点的左右指针指向左右子树递归函数的返回值，当该二叉树判断为零树（左右指针指向空指针且其根节点的值为0），则返回空指针，反之则返回根节点。

c++实现（1）有点繁琐

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        //根节点为空，则直接返回空
        if (root == nullptr){
            return nullptr;
        }
        //声明左右子树递归函数的返回值
        TreeNode* left = pruneTree(root->left);
        TreeNode* right = pruneTree(root->right);
        //二叉树判断为零树（左右指针指向空指针且其根节点的值为 0）
        if(root->val == 0 && left==nullptr && right==nullptr){
            return nullptr;
        } 
        //根节点的左右指针指向左右子树递归函数的返回值
        root->left = left;
        root->right = right;
        return root;
    }
};

c++实现（2）

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
      //如果根节点的左指针不为空
      if(root->left!=nullptr)
      {
          //根节点的左指针指向左子树递归函数的返回值
          root->left=pruneTree(root->left);
      }
      //如果根节点的右指针不为空
      if(root->right!=nullptr)
      {
          //根节点的右指针指向右子树递归函数的返回值
          root->right=pruneTree(root->right);
      }
      if(root->val==1 || root->left!=nullptr || root->right!=nullptr) {
          return root;
      }else{
          return nullptr;
      }
    }
};

golang实现

func pruneTree(root *TreeNode) *TreeNode {
    if root.Left != nil {
        root.Left=pruneTree(root.Left)
    }
    if root.Right != nil {
        root.Right = pruneTree(root.Right)
    }
    if root.Val == 1 || root.Left!=nil || root.Right!=nil {
        return root
    }else{
        return nil
    }
}