“This is the 27th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

Title 1

112. Sum of paths

You are given the root node of the binary tree and an integer targetSum representing the targetSum. Determine if there is a path from the root node to the leaf node in the tree. The sum of all nodes in the path equals the target and targetSum.

A leaf node is a node that has no children.

 

Example 1:

Input: root = [13,4,7,2 5,4,8,11, null, null, null, null, 1], targetSum = 22 output: true

Example 2:

Input: root = [1,2,3], targetSum = 5 output: false

Example 3:

Input: root = [1,2], targetSum = 0 output: false

Tip:

The number of nodes in the tree is in the range [0, 5000] -1000 <= node. val <= 1000 -1000 <= targetSum <= 1000

Ask questions

  • What is a leaf node?
  • How to find a path where all nodes add up to the target and targetSum?

Analysis of the

  • A leaf node is a node at the last level of a binary tree with no children
  • Recursively traverses the binary treetargetSum = targetSum - root.val, when traversing to the leaf node, judge the current noderootWhether or nottargetSumEqual. Equal means found

Pseudo code

  • In the first place to judgerootWhether it isnullfornullDirect returnfasle
  • If the current node does not exist, returns the value of the current node andtargetSumAre equal
  • The left and right nodes of the pre-recursive node,targetSumfortargetSum - root.val

Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {boolean} */ var hasPathSum = function(root, targetSum) { if(! root) return false if(! root.left && ! root.right) return root.val == targetSum return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val) };Copy the code

Topic 2

222. Number of nodes in a complete binary tree

Find the number of nodes in a * complete binary tree.

A complete binary tree is defined as follows: In a complete binary tree, the number of nodes in each layer reaches the maximum except that the lowest node may not be filled, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is layer H, this layer contains 1 to 2h nodes.

 

Example 1:

Input: root = [1,2,3,4,5,6] output: 6

Example 2:

Input: root = [] Output: 0

Example 3:

Input: root = [1] Output: 1

 

Tip:

  • The number of nodes in the tree ranges from[0, 5 * 104]
  • 0 <= Node.val <= 5 * 104
  • The problem data guarantees that the input tree is a complete binary tree

Ask questions

  • What is a complete binary tree?
  • How do I count the number of nodes?

Analysis of the

  • In simple terms, a complete binary tree is full except for the last layer, which is sometimes full, and the nodes in the last layer need to be further to the left
  • Recursively traversing the binary tree increments each time it traverses it

Pseudo code

  • In the first place to judgerootWhether it isnullfornullDirect return0
  • Recurse to the left and right of the front node, and+ 1

Code implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if(root == null) return 0
    return countNodes(root.left) + countNodes(root.right) + 1
};
Copy the code