【leetcode】【剑指offer Ⅱ】047. 二叉树剪枝

问题描述：

• 给定一个二叉树根节点 root，树的每个节点的值要么是 0，要么是 1。
  • 剪除该二叉树中所有节点的值为 0 的子树。
  • 节点 node 的子树为 node 本身，以及所有 node 的后代。

核心思路：

• 该题用递归来做比较方便。
  • 递归进入左子，并将递归返回的结果作为新的左子，即 root->left = dfs(root->left);。
  • 之所以要重置左子，是因为左子可能是全为 0 的子树，如果左子树中数值全为 0，则将左子置为空。
  • 而在递归的最后，判断当前节点 root 数值是否为 0，以及左右子是否为空，如果为 0 且左右子均空，则将空指针 nullptr 作为结果返回，否则返回当前节点 root。
• 树的递归其实就是链表的递归，当时链表的递归需要考虑的是三样，即停止条件、普通递归情况、返回结果；树的递归考量的内容也是一样的。

代码实现：

class Solution
{
public:
    TreeNode* pruneTree(TreeNode* root)
    {
        if(!root) return root;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        return (!root->left and !root->right and root->val == 0) ? nullptr : root;
    }
};
1
2
3
4
5
6
7
8
9
10
11