110. Balanced binary trees (prioritize recursion)
Given a binary tree, determine whether it is a balanced binary tree.
Balanced binary tree A balanced binary tree is a tree in which the depths of the left and right subtrees of all the nodes of the tree do not differ by more than one.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Tip:
The number of nodes in the tree is in the range [0, 5000].
-104 <= <= 104
correct solution (a math. equation)
Since the requirement is to compare heights, it is inevitably going to be a back-order traversal.
- Clarify the parameters and return values of recursive functions
Parameters: current incoming node. Return value: the height of the tree with the current incoming node as the root node.
So how do you mark whether the difference between the left and right subtrees is greater than 1?
If the binary tree whose current incoming node is the root node is no longer a binary balanced tree, it makes no sense to return the height.
So if it is no longer a binary balanced tree, you can return -1 to mark that it no longer conforms to the rules of balanced trees. - Clarification of termination conditions
Recursive process is still encountered in the empty node for the termination, return 0, that the current node for the root node of the tree height of 0 - Clarify the logic of single-level recursion
How do you determine whether a binary tree with the current incoming node as its root node is a balanced binary tree? The difference between the height of its left subtree and the height of its right subtree, of course.
Find the heights of its left and right subtrees, respectively, and then return the height of the current binary tree if the difference is less than or equal to 1. Otherwise, return -1 to indicate that it is no longer a binary balanced tree.
Upper code (●'◡'●)
class Solution {
public:
// Returns the height of the binary tree with this node as the root node，If it is not a balanced binary tree then return-1
int getHeight(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right);
if (rightHeight == -1) return -1;
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
257. All paths in a binary tree
Given the root node of a binary tree, return all paths from the root node to the leaf nodes in any order.
Leaf node A node that has no children.
Example 1:
Input: root = [1,2,3,null,5]
Output: ["1->2->5", "1->3"]
Example 2:
Input: root = [1]
Output: ["1"]
Tip:
The number of nodes in the tree is in the range [1, 100].
-100 <= <= 100
correct solution (a math. equation)
This question asks for a path from the root node to a leaf, so it requires a preorder traversal so that it is easy to get the parent node to point to the child node and find the corresponding path.
Backtracking will be involved for the first time in this question, as we are going to record the paths and need to backtrack to go back one path and enter another.
- Recursive Function Arguments and Return Values
To pass in the root node, the path to record each path, and the result to store the result set, where the recursion doesn't need a return value. - Determining recursive termination conditions
When cur is not null and both its left and right children are null, the leaf node is found.
Here we are using the vector structure path to record the path, so we have to convert the path of the vector structure to string format and put this string into the result.
So why do you use a vector structure to record paths? The reason is that when dealing with single-level recursive logic below, you have to do backtracking, and using vectors makes it easier to do that. - Determining single-level recursive logic
Because it's a preorder traversal, you need to deal with the intermediate nodes first, which are the nodes on the path we're trying to record, and put them into path first.
Then there is the process of recursion and backtracking, as stated above there is no judgment on whether cur is empty or not, so when recursing here, if it is empty the next level of recursion is not performed.
So the recursion is preceded by a judgment statement as to whether the following node to be recursed is empty or not
At this point it's not over, the recursion is over, you have to backtrack, because path can't keep joining nodes, it has to delete nodes before it can join new nodes.
So what's the backtracking going to be?
We know that backtracking and recursion are one-to-one; for there to be a recursion, there has to be a backtracking.
That's why backtracking should always go together with recursion; the furthest distance in the world is when you're inside the parentheses and I'm outside them!
Upcode (●'◡'●)
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // center
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
return;
}
if (cur->left) traversal(cur->left, path + "->", result); // unorthodox
if (cur->right) traversal(cur->right, path + "->", result); // right (-hand)
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
404. sum of left leaves
Given the root node root of a binary tree, return the sum of all the left leaves.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: In this binary tree, there are two left leaves, 9 and 15, so 24 is returned.
Example 2.
Input: root = [1]
Output: 0
Tip.
Number of nodes in the range [1, 1000].
-1000 <= <= 1000
The first thing to note is that you are judging the left leaf, not the left node of the binary tree, so don't come up thinking about hierarchical traversal.
Explicit definition of left leaf: if the left child of node A is not null and the left and right children of the left child are both null (indicating a leaf node), then the left child of node A is a left leaf node; the
The traversal order of the recursion is a backward traversal (left and right center) because the sum of the left leaf values is to be summed cumulatively by the return value of the recursive function.
- Determining the parameters and return values of a recursive function
To determine the sum of the left leaf nodes of a tree, then must be passed to the root node of the tree, the return value of the recursive function is the sum of the values, so int
Just use the function given in the title. - Determination of termination conditions
If the traversal reaches an empty node, then the left leaf value must be 0; the
Note that only if the currently traversed node is a parent node can you determine if its children are left leaves. So if the currently traversed node is a leaf node, then its left leaf must be 0 as well; and - Determining the logic of single-level recursion
When a left leaf node is encountered, the value is recorded, and then the sum of the left leaves of the left subtree and the sum of the left leaves of the right subtree is recursively computed, and the sum of the left leaves of the whole tree is added.
Upper code (●'◡'●)
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
int leftValue = 0;
if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
leftValue = root->left->val;
}
return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};
It's not easy to write a blog, so please give me some support 8~!