为什么我的递归解决方案修剪二叉树不工作?

Question

问题链接:https://leetcode.com/problems/binary-tree-pruning/

基本上，给定二叉树的根，返回同一棵树，其中(给定树的)所有不包含1的子树都已被删除。

我代码:

/**
* 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:
TreeNode* pruneTree(TreeNode* root) {
recurse(root);
return root;
}

bool recurse(TreeNode* &root) {
if (root == nullptr)
return false;
cout<<"val: "<<root->val<<" ";
if (recurse(root->left) == false && recurse(root->right) == false && root->val==0)
{
root = nullptr;
return false;
}
return true;
}

};

使用print语句，我发现在找到一个要删除的节点后，它将其删除，然后停止递归并返回树。为什么会这样呢?

Answer 1

if (  ... )

为了使if语句求值为true,if语句中的两个递归调用必须返回false。这个if语句使用布尔&&运算符。在c++中，布尔&&运算符要求其左右两侧的表达式都为真，在这种情况下，只有递归调用返回false时才会发生这种情况。如果任何递归调用返回true，则逻辑上不可能将if语句求值为true。

当if语句为false时，下一条语句为:

return true;

因此，只要递归调用的第一个return返回true，无论出于何种原因，所有正在进行的递归调用必须导致调用if语句，最终if语句求值为false，以及相应的递归调用return true;。

游戏结束。