This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

In front of the more basic binary tree questions, there is a need for children’s shoes please blunt binary tree brush questions (a), this article to write a little bit more complex.

I. The sum of paths

112. Sum of paths

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

A leaf node is a node that has no children.

Example 1:

Enter: root = [5.4.8.11.null.13.4.7.2.null.null.null.1], targetSum = 22Output:true
Copy the code

Example 2:

Enter: root = [1.2.3], targetSum = 5Output:false
Copy the code

Example 3:

Enter: root = [1.2], targetSum = 0Output:false
Copy the code

Tip:

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

Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Their thinking

Return true if the leaves and the current targetSum are equal. Return false if the leaves and the current targetSum are equal.

Return true if one of the left and right subtrees finds the path, false otherwise.

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 == null) return false;
    // If the current node is a leaf (no left or right nodes), return whether the value of this node is equal to the current targetSum
    if(root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    targetSum = targetSum - root.val;
    // Iterate through the current left and right nodes recursively
    return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};
Copy the code

Two, judge the balanced binary tree

Balanced binary trees

Given a binary tree, determine whether it is a highly balanced binary tree.

In this case, a highly balanced binary tree is defined as:

The absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.

 

Example 1:

Enter: root = [3.9.20.null.null.15.7] output:true
Copy the code

Example 2:

Enter: root = [1.2.2.3.3.null.null.4.4] output:false
Copy the code

Example 3:

Input: root = [] Output:true
Copy the code

Tip:

  • The number of nodes in the tree is in the range [0, 5000]
  • -104 <= Node.val <= 104

Source: LeetCode link: leetcode-cn.com/problems/ba… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Their thinking

We recursively traverse all the nodes, returning the heights of the left and right subtrees. When the height difference between the left and right subtrees is less than one, it is a balanced binary tree.

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) * } */
var dfs = function(root) {
    if(root == null) return 0;
    // Get the left and right subtree height
    let leftHeight = dfs(root.left);
    let rightHeight = dfs(root.right);
    // If the nodes traversed by the current surface are unbalanced, the whole binary tree is not a balanced tree, return -2 directly
    // Return -2 for an unbalanced binary tree
    if(leftHeight == -2 || rightHeight == -2) return -2;
    // If the absolute value of the height difference between two subtrees does not exceed 1, then it is not a balanced binary tree and returns -2
    if(Math.abs(leftHeight - rightHeight) > 1) {
        return -2
    }
    // Return the height of the current subtree
    return Math.max(leftHeight, rightHeight) + 1;
}
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isBalanced = function(root) {
    // If you do not return -2 + 1 = -1, prove to be a balanced binary tree
    return dfs(root) >= 0
};
Copy the code

Iii. Sequence traversal of binary tree II

107. Sequential traversal of binary trees II

Given a binary tree, return a bottom-up sequential traversal of its node values. (that is, according to the layer from the leaf node to the root node layer, layer by layer from left to right traversal)

For example, given a binary tree [3,9,20,null,null,15,7],

   3
   / \
  9  20
    /  \
   15   7
Copy the code

Return its bottom-up sequence traversal as:

[[15.7],
  [9.20],
  [3]]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Their thinking

We recursively iterate through all the nodes from top to bottom, mark the level of each node, and place the current node we have traversed at that level. After the whole binary tree is obtained from the top down, the position is reversed.

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) * } */

var dfs = function(root, ans, deep) {
    if(root == null) return;
    if(deep == ans.length) ans.push([]);
    ans[deep].push(root.val);
    dfs(root.left, ans, deep + 1);
    dfs(root.right, ans, deep + 1);
}
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrderBottom = function(root) {
    let ans = [];
    dfs(root, ans, 0);
    for(let i = 0, j = ans.length - 1; i < j; i++, j--) {
        let temp = ans[i];
        ans[i] = ans[j];
        ans[j] = temp;
    }
    return ans;
};
Copy the code