Make writing a habit together! This is the third day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

On the first day of qingming Holiday, new articles continue

The weather is just, lush trees, not as good as a binary tree – binary tree pruning ~🐶

Topic:

I give you the root of the binary tree, root, and the value of each node of the tree is either 0 or 1.

Returns the original binary tree that removes all subtrees that do not contain 1.

The subtree of a node adds the descendants of all nodes to the node itself.

Example 1: Input: root = [1, NULL,0,0,1] Output: [1, NULL,0, NULL,1] Description: Only red nodes meet the condition all subtrees that do not contain 1. The picture on the right shows the answers returned.Copy the code

Example 2: Input: root = [1,0,1,0,0, 1] Output: [1, NULL,1, NULL,1]Copy the code

Example 3: input: root =,1,0,1,1,0,1,0 [1] output: [1,1,0,1,1, null, 1]Copy the code

【 答 案 】

If the value of all nodes in the binary tree is 0, then how can we know that the value of all nodes in the binary tree is 0? Recursion only needs to consider what the current node needs to do. Whether the current node can be pruned depends on the value of the left and right subtrees and the current node.

The difficulty of this problem is that the pruning should continue until there is no leaf node with a value of 0. The highest efficiency can be achieved only by traversing the position from the bottom up.

【JS implementation 】

/** * @param {TreeNode} root * @return {TreeNode} */ var pruneTree = function(root) {// If (root == null) { return root; } root.left = pruneTree(root.left); root.right = pruneTree(root.right); // If (!) if (! root.left && ! root.right && root.val == 0) { return null; } return root; };Copy the code

“Verification”

After the sequence traversal + recursion, simple implementation, like 👍