https://blog.csdn.net/2601_95366422/article/details/159243146一.题目814. 二叉树剪枝 - 力扣LeetCode二.思路讲解2.1 审题本题要求对一棵二叉树进行剪枝其中每个节点的值只能是0或1。剪枝的规则是如果一棵子树中所有节点的值都为 0那么将这棵子树整个移除。换句话说我们需要从叶子节点向上检查如果某个节点及其所有后代都不包含 1则将该节点置为nullptr使其父节点不再指向它。2.2 子问题解决对于二叉树的问题我们通常采用后序遍历的方式因为要先知道左右子树的情况才能决定当前节点是否需要被剪掉。具体思路如下首先递归地处理左子树和右子树得到它们剪枝后的结果。这一步我们相信递归能正确完成。然后检查当前节点如果左子树剪枝后为空且右子树剪枝后为空且当前节点的值本身为 0说明以当前节点为根的整棵子树都不包含 1那么应该将当前节点删除即返回nullptr给父节点。否则当前节点需要保留并连接上剪枝后的左右子树然后返回当前节点。通过这种方式我们自底向上地完成了剪枝且每个节点只需要访问一次。2.3 递归终止条件递归的终止条件是当节点为空nullptr时直接返回nullptr。因为空节点既没有值也不属于任何子树作为递归的基础情况非常自然。三.代码演示/** * 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) { //1.终止条件 if(root nullptr) return nullptr; //2.子问题解决 root-left pruneTree(root-left); root-right pruneTree(root-right); if(root-left nullptr root-right nullptr root-val 0) { return nullptr; } return root; } };四.代码讲解一、递归函数设计我们定义递归函数pruneTree(TreeNode* root)它的含义是对以root为根的二叉树进行剪枝并返回剪枝后新的根节点可能为nullptr。剪枝规则是移除所有不包含1的子树。由于我们需要先知道左右子树的情况才能决定当前节点是否保留因此采用后序遍历的方式。二、递归终止条件当当前节点为空root nullptr时直接返回nullptr。这是递归的基础情况因为空节点自然不需要剪枝也没有任何值。三、递归步骤分解对于非空节点按照以下步骤进行后序遍历递归处理左子树调用pruneTree(root-left)对左子树进行剪枝并将结果重新赋值给root-left。这一步会移除左子树中所有全零子树返回剪枝后的左子节点可能为空。我们相信递归能正确完成。递归处理右子树同理调用pruneTree(root-right)对右子树剪枝结果赋给root-right。判断当前节点是否需要被移除在左右子树都处理完毕后检查当前节点是否满足移除条件左子树为空、右子树为空、且当前节点的值为0。如果三者同时成立说明以当前节点为根的整棵子树都不包含1因此应该将当前节点移除返回nullptr给父节点。返回保留的节点如果不满足移除条件则当前节点需要保留直接返回root。此时它的左右子树已经过剪枝结构正确。四、关键细节后序遍历的必要性只有先知道左右子树是否为空才能判断当前节点是否应该被删除。这是由剪枝规则决定的。。指针更新通过root-left pruneTree(root-left)的方式将剪枝后的子树直接挂回当前节点实现了原地修改。移除条件注意条件是左右子树都为空且当前节点值为0这意味着整棵子树都无1。如果当前节点值为1即使左右为空也保留如果某子树非空说明该子树有1当前节点也保留。