“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
Whether the symmetrical
Given a binary tree, check whether it is mirror – symmetric.
The figure above shows a symmetric binary tree
The binary tree above is not mirrored
Train of thought
To determine whether it is a mirror image, we need to determine whether the inside and outside sides of the binary tree are the same.
It is necessary to determine whether the inner and outer sides of the left subtree and the right subtree under the root node are equal. The method of comparison is to compare the “left-right-center” nodes of the left subtree with the “right-left-center” nodes of the right subtree.
This problem is more convenient to solve in a recursive way, the recursive idea is as follows:
- Since we want to compare whether two subtrees are mirror images, the recursive parameters are two, namely, the left subtree node and the right subtree node
- There are three termination conditions:
Return false if the left node is not empty and the right node is not empty. Return false if the left node is not empty and the right node is not empty
- If none of the above conditions are met, the recursive logic is entered again
Code implementation
public boolean isSymmetric1(TreeNode root) {
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right) {
if (left == null&& right ! =null) {
return false;
}
if(left ! =null && right == null) {
return false;
}
if (left == null && right == null) {
return true;
}
if(left.val ! = right.val) {return false;
}
// Compare the outside
boolean compareOutside = compare(left.left, right.right);
// Compare the inside
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
Copy the codeTime complexity: O(N), where N is the number of nodes in the tree. Access each node once.
Space complexity: O(H), where H is the height of the tree
The maximum depth of a binary tree
Given a binary tree, find its maximum depth.
Train of thought
The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.
We can solve this problem recursively:
1. The recursive function takes the root node of the binary tree as its parameter and returns the height of the binary tree. 2. The termination condition of recursion is that when the node is empty, the return height is 0; 3. Find the height of the left subtree and then the height of the right subtree. The maximum height of the two heights +1 is the maximum depth of the binary tree.
The code is as follows:
class solution {
public:
int getdepth(treenode node) {
if (node == null) return 0;
int leftdepth = getdepth(node.left); / / left
int rightdepth = getdepth(node.right); / / right
int depth = 1 + Math.max(leftdepth, rightdepth); / /
return depth;
}
int maxdepth(treenode root) {
returngetdepth(root); }};Copy the codeTime complexity: O(N), where N is the number of nodes in the tree. Access each node once.
Space complexity: O(H), where H is the height of the tree
Similarly, this method is suitable for finding the maximum depth of n-fork tree, and the code is as follows:
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node(a) {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) { val = _val; children = _children; }};class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
} else if (root.children.isEmpty()) {
return 1;
} else {
List<Integer> heights = new LinkedList<>();
// Loop to find the height of each subtree
for (Node item : root.children) {
heights.add(maxDepth(item));
}
return Collections.max(heights) + 1; }}}Copy the codeTime complexity: O(N), where N is the number of nodes in the tree. Access each node once.
Space complexity: O(H), where H is the height of the tree
The minimum depth of a binary tree
Note: The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
One of the things that needs to be explained here is that from the root to the nearest leaf, if the root has no left or right subtree, a lot of people think that the minimum depth is 1, and that’s not true. The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
It can be seen that the difference between finding the minimum depth of a binary tree and finding the maximum depth of a binary tree mainly lies in dealing with the logic that the left and right children are not empty.
The code is as follows:
class Solution {
/** * MaxDepth is a bit more complicated than MaxDepth because the minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node */
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// The left and right nodes are not null
return Math.min(leftDepth, rightDepth) + 1; }}Copy the codeTime complexity: O(N), where N is the number of nodes in the tree. Access each node once.
Space complexity: O(H), where H is the height of the tree.
Find how many nodes there are in a binary tree
A complete binary tree is given and the number of nodes in the tree is obtained.
This problem can be solved by finding the maximum depth of the binary tree, the code is as follows:
class solution {
public:
int getdepth(treenode node) {
if (node == null) return 0;
int leftdepth = getdepth(node.left); / / left
int rightdepth = getdepth(node.right); / / right
int depth = 1 + leftdepth, rightdepth; / /
return depth;
}
int maxdepth(treenode root) {
returngetdepth(root); }};Copy the codeTime complexity: O(n), where n is the number of nodes in the binary tree Space complexity: O(h), where h is the height of the 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 is no more than 1.
Train of thought
Since we need to be relatively high, we can use the way of post-order traversal.
- If the return value of the left and right subtrees is > 1, we return -1, indicating that it is no longer a balanced binary tree.
- The termination condition of recursion is that an empty node is encountered, then return 0, indicating that the current node is the root node and its height is 0.
- The single-layer recursive logic is, the height of the left and right subtrees is calculated respectively. If the difference is less than or equal to 1, the height of the current binary tree is returned; otherwise, -1 is returned, indicating that it is no longer a binary tree.
The code is as follows:
class Solution {
/** * recursion */
public boolean isBalanced(TreeNode root) {
returngetHeight(root) ! = -1;
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
// If the height difference between left and right subtrees is greater than 1, return-1 indicates that the tree is no longer balanced
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1; }}Copy the codeAll the ways in a binary tree
Given a binary tree, return all paths from the root node to the leaf node.
Train of thought
The path from the root node to the leaf node needs to be traversed in advance.
- Determine the recursive arguments and return values for the passed root node, record the array path of node values for each path, and the array res of path results;
- Terminates when a leaf node is encountered, and converts the value in the path node value array to a string, which is then added to the result array.
- The single-layer logic of recursion is, because it is a front-order traversal: middle-left-right, so the middle nodes are first processed and added to the path, and then the left and right subtrees are recursively processed and backtracked after recursion.
The code is as follows:
/ / solution
class Solution {
/** * recursion */
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
List<Integer> paths = new ArrayList<>();
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
paths.add(root.val);
// Leaves
if (root.left == null && root.right == null) {
/ / output
StringBuilder sb = new StringBuilder();
for (int i = 0; i < paths.size() - 1; i++) {
sb.append(paths.get(i)).append("- >");
}
sb.append(paths.get(paths.size() - 1));
res.add(sb.toString());
return;
}
if(root.left ! =null) {
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);/ / back
}
if(root.right ! =null) {
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);/ / back}}}Copy the codeSum of left leaves
Computes the sum of all left leaves of a given binary tree.
Train of thought
First of all, to determine whether the binary tree has left leaf or not, we must judge whether the left child is the left leaf by the parent node of the node. The judging code is as follows:
if(root.left ! =null && root.left.left == null && root.left.right == null) { / /
midValue = root.left.val;
}
Copy the codeFind the sum of values of all left leaf nodes by post-order traversal, and the recursion is as follows:
- The recursive function takes the root node as its parameter and returns the sum of the left leaf nodes.
- Recursive termination condition root == null returns 0;
- Single-layer recursive logic: when the left leaf node is encountered, the value is recorded, and then the sum of the left leaf of the left subtree is obtained recursively, and the sum of the left leaf of the right subtree is the sum of the left leaf of the whole tree.
The code is as follows:
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int leftValue = sumOfLeftLeaves(root.left); / / left
int rightValue = sumOfLeftLeaves(root.right); / / right
int midValue = 0;
if(root.left ! =null && root.left.left == null && root.left.right == null) { / /
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue;
returnsum; }}Copy the codeThe value in the lower left corner
Given a binary tree, find the leftmost value in the last row of the tree.
Train of thought
The easiest way to do this is to go through the sequence, to the left of the last line.
But it can also be achieved by recursion. First of all, it can be made clear that the deepest leaf node must be the last line, so how to find the leftmost one? We can use a front-order traversal to search first from the left.
- Specify the arguments and return values of the recursive function: the arguments are the root node passed in, and an int variable to record the maximum depth. Return void;
- When the leaf node is encountered, it is the termination condition and the maximum depth is counted.
- Determine the single-layer recursive logic, and if it is not a leaf node, continue traversing the left and right subtrees and remember to backtrack;
The code is as follows:
/ / the recursive method
class Solution {
private int Deep = -1;
private int value = 0;
public int findBottomLeftValue(TreeNode root) {
value = root.val;
findLeftValue(root,0);
return value;
}
private void findLeftValue (TreeNode root,int deep) {
if (root == null) return;
if (root.left == null && root.right == null) {
if(deep > Deep) { value = root.val; Deep = deep; }}if(root.left ! =null) findLeftValue(root.left,deep + 1);
if(root.right ! =null) findLeftValue(root.right,deep + 1); }}Copy the codeTotal strength of road 1
Given a binary tree and a destination sum, determine whether there is a path from the root node to the leaf node in the tree. The sum of the values of all nodes along the path equals the destination sum.
Train of thought
Use recursion to solve this problem:
- Determine the pass parameter and return value of the recursive function: the parameter is the passed root node and the count variable, which needs to subtract the value of the current node every time it recurses, and judge whether the value of the leaf node is consistent with it when it finally meets the leaf node. If so, it means that the path has been found. The return value is bool;
- A recursive function terminates if it returns true when a leaf node is encountered and the count variable equals the value of the leaf node.
- The single-layer recursive logic is: traverse the left and right subtrees and backtrack
The code is as follows:
class solution {
public boolean haspathsum(treenode root, int targetsum) {
if (root == null) {
return false;
}
targetsum -= root.val;
// Leaves
if (root.left == null && root.right == null) {
return targetsum == 0;
}
if(root.left ! =null) {
boolean left = haspathsum(root.left, targetsum);
if (left) {// Found
return true; }}if(root.right ! =null) {
boolean right = haspathsum(root.right, targetsum);
if (right) {// Found
return true; }}return false; }}// Simplified code
class solution {
public boolean haspathsum(treenode root, int targetsum) {
if (root == null) return false; // Exit if empty
// the leaf node determines whether it matches
if (root.left == null && root.right == null) return root.val == targetsum;
// Find the sum of the paths of both branches
returnhaspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val); }}Copy the codeSum of paths 2
Given a binary tree and a destination sum, find all paths from the root node to the leaf node where the sum of paths equals the given destination sum.
Train of thought
The solution is similar to the previous problem, except that you need to record the path.
The code is as follows:
class solution {
public list<list<integer>> pathsum(treenode root, int targetsum) {
list<list<integer>> res = new arraylist<>();
if (root == null) return res; // Non-null judgment
list<integer> path = new linkedlist<>();
preorderdfs(root, targetsum, res, path);
return res;
}
public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
path.add(root.val);
// A leaf node is encountered
if (root.left == null && root.right == null) {
// The path with and targetsum is found
if (targetsum - root.val == 0) {
res.add(new arraylist<>(path));
}
return; // If and are not targetsum, return
}
if(root.left ! =null) {
preorderdfs(root.left, targetsum - root.val, res, path);
path.remove(path.size() - 1); / / back
}
if(root.right ! =null) {
preorderdfs(root.right, targetsum - root.val, res, path);
path.remove(path.size() - 1); / / back}}}Copy the codeThe last
Ok, so that’s the end of the summary of binary tree properties. I believe that after reading this article, you will have a certain understanding of the properties of binary trees, thank you for reading.
Previous articles:
- StoreKit2 smells this good? Yeah, I tried it. It smells good
- After reading this article, I am no longer afraid of being asked how to construct a binary tree.
- The game guys are trying to get people to pay again. That’s bad!
- Take you rolled a netease holding cloud music home | adapter
- Netease Cloud Music Home Page (3)
- Netease Cloud Music Home Page (2)
- Netease Cloud Music Home Page (a)
- Does the code need comments? Write and you lose
- I would not study in Codable for a long time. They are for fun
- IOS handles web data gracefully. Do you really? Why don’t you read this one
- UICollectionView custom layout! This one is enough
Please drink a cup ☕️ + attention oh ~
- After reading, remember to give me a thumbs-up oh, there is 👍 power
- Follow the public number – HelloWorld Jie Shao, the first time push new posture
Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~