This series is mainly to record the process of my brush questions. The key is to solve each type of problem step by step, according to this order of basic every problem can be done. Rather than a solution to a problem, so it is suitable for people who plan to brush a lot of reference. Binomial tree related to the order of brush questions is a reference code catalog, interested in the public can download the corresponding PDF.
LeetCode_ Binary Tree Brush Problem Note 4(Java)
LeetCode_ Binary Tree Brush problem Note 3(Java)
LeetCode_ Binary Tree Brush Problem Notes 2(Java)
LeetCode_ Binary Tree Brush problem Notes 1(Java)
The following 12 problems need some basic binary tree traversal, and they are not difficult.
226. Flip the binary tree
Difficulty is simple
Flip a binary tree.
Example:
Input:
4 / \ 27 / \ / \ 1 3 6 9Copy the codeOutput:
4 / \ 7 2 / \ / 9 6 3 1Copy the codeNote: This question was inspired by Max Howell’s original question:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t flip a binary tree on a whiteboard during an interview. That’s too bad.
Train of thought
This is an algorithm that stumped Max Howell ！！！！
With note 1, it’s not hard to imagine that you can solve it using traversal and swap. Traversal is actually more comfortable to write recursively, so let’s use pre-order traversal. The code is simple:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)return root;
swapRootChildren(root);
invertTree(root.left);
invertTree(root.right);
return root;
}
// Switch the position of the two child nodes under the current node
private void swapRootChildren(TreeNode root){ TreeNode temp = root.left; root.left = root.right; root.right = temp; }}Copy the codeLook at the performance is ok:
101. Symmetric binary trees
Easy 1240
Given a binary tree, check whether it is mirror – symmetric.
For example, binary trees [1,2,2,3,4,4,3] are symmetric.
1
/ \
2 2
/ \ / \
3 4 4 3
Copy the codeBut the following [1,2,2,null,3,null,3] is not mirror symmetric:
1 / \ 2 2\3 3Copy the codeTrain of thought
Mirror symmetry means that the value of the node on the left is equal to the value of the node on the right. If all of them satisfy it’s a symmetric binary tree.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root,root);
}
// Start from root and walk down in two directions and compare
public boolean check(TreeNode l,TreeNode r){
// If the primary null node is symmetric, and both the left and right nodes are null, you can exit recursion
if(l==null&&r==null) return true;
if(l==null||r==null) return false;
// Note that the recursive elements need symmetry (mirror image) l.ight -- r.left. l.ight -- R.ight
returnl.val==r.val&&check(l.left,r.right)&&check(l.right,r.left); }}Copy the code
104. Maximum depth of a binary tree
The difficulty is simple 792
Given a binary tree, find its maximum depth.
The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.
Note: Leaf nodes are nodes that have no child nodes.
Example: given a binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Copy the codeReturns its maximum depth of 3.
Train of thought
In this case, the current depth is recorded when each leaf node is reached through depth first traversal. Finally get the maximum depth:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
private int maxD;
public int maxDepth(TreeNode root) {
if(root==null) return 0;
preoder(root,0);
return maxD;
}
private void preoder(TreeNode root,int deep){
if(root==null){
maxD=Math.max(deep,maxD);
return;
}
deep++;
preoder(root.left,deep);
preoder(root.right,deep);
// This is actually backtrackingdeep--; }}Copy the code
In fact, this problem uses ** sequence traversal, ** is more logical, because the sequence traversal is to go down one layer, go to the last layer must be the maximum depth:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque();
if(root! =null){
queue.add(root);
}
int depth =0;
while(! queue.isEmpty()){int n =queue.size();
// Go into the whilie one time just to add a layer
depth++;
for(int i = 0; i<n; i++){ TreeNode node = queue.poll();if(node.left! =null){
queue.add(node.left);
}
if(node.right! =null){ queue.add(node.right); }}}returndepth; }}Copy the code559. The maximum depth of the N fork tree
The difficulty is simple
Given an n-fork tree, find its maximum depth.
The maximum depth is the total number of nodes along the longest path from the root node to the farthest leaf node.
N fork tree input is serialized in sequential traversal, with each set of child nodes separated by null values (see example).
Example 1:
Input: root = [1,null,3,2,4,null,5,6] output: 3Copy the codeExample 2:
Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] output: 5Copy the codeTip:
- The depth of the tree cannot exceed
1000。 - The number of nodes in the tree is located
[0, 104]In between.
Train of thought
The maximum depth of a binary tree is 104. The maximum depth of a binary tree is 104. The maximum depth of a binary tree is 104. The sequence traversal will time out:
/* // Definition for a Node. class Node { public int val; public List
children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List
_children) { val = _val; children = _children; }}; * /
class Solution {
private int maxD;
public int maxDepth(Node root) {
if(root==null) return 0;
preoder(root,0);
return maxD;
}
private void preoder(Node root,int deep){
deep++;
// Pay attention to the judgment condition of the leaf node
if(root.children.isEmpty()){
maxD=Math.max(deep,maxD);
return;
}
for(Node child: root.children){ preoder(child,deep); } deep--; }}Copy the code111. Minimum depth of a binary tree
The difficulty is simple 453
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.
** Note: ** leaf nodes refer to nodes that have no child nodes.
Example 1:
Input: root = [3,9,20,null,null,15,7] output: 2Copy the codeExample 2:
Input: root = [2, null, 3, null, 4, null, 5, null, 6] output: 5Copy the codeTip:
- The number of nodes in the tree ranges from
[0, 105]内 -1000 <= Node.val <= 1000
Train of thought
The maximum depth of a binary tree is 104. * *. What is a leaf node? A node with no children is called a leaf node, where both left and right are null
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
private int minD=Integer.MAX_VALUE;
public int minDepth(TreeNode root) {
if(root==null) return 0;
preoder(root,0);
return minD;
}
private void preoder(TreeNode root,int deep){
if(root==null) {// This cannot be considered a path
return;
}
deep++;
// This is the leaf node
if(root.left==null&&root.right==null){
minD=Math.min(deep,minD);
return; } preoder(root.left,deep); preoder(root.right,deep); deep--; }}Copy the code222. Number of nodes in a complete binary tree
The difficulty is medium 434
Given the root node of a complete binary tree, find the number of nodes in the 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: 6Copy the codeExample 2:
Input: root = [] Output: 0Copy the codeExample 3:
Input: root = [1] Output: 1Copy the codeTip:
- 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
Train of thought
This problem can be solved using ordinary binary trees:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
return 1+ countNodes(root.left)+countNodes(root.right); }}Copy the codeThis problem can also be solved by the properties of complete binary trees. A complete binary tree must be made up of a full binary tree. The number of nodes in a full binary tree only needs to know the tree depth (H) : 2<< h-1 (2 ^ H) :
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
TreeNode left =root.left;
TreeNode right =root.right;
int leftHeight =0;
while(left! =null){
leftHeight++;
left=left.left;
}
int rightHeight = 0;
while(right! =null){
rightHeight++;
right=right.right;
}
// Full binary tree with the same height
if(leftHeight==rightHeight){
return (2<<leftHeight)-1;
}
// Not all parts of the binary tree are added one by one
return countNodes(root.left)+countNodes(root.right)+1; }}Copy the code
110. Balanced binary trees
The difficulty is simple 593
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 in a binary tree is no more than 1.
Example 1:
Input: root = [3,9,20,null,null,15,7] output: trueCopy the codeExample 2:
Input: root = [1,2,2,3,3,null,null,4,4] output: falseCopy the codeExample 3:
Input: root = [] Output: trueCopy the codeTip:
- The number of nodes in the tree is in the range
[0, 5000]内 -104 <= Node.val <= 104
Train of thought
It is necessary to determine whether the depth difference between left and right of each non-leaf node is less than 1.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) {return true;
}
return Math.abs(getNodeDepth(root.left)-getNodeDepth(root.right))<=1
&&isBalanced(root.left)
&&isBalanced(root.right);
}
// Get the depth of the current node (note that the depth is the largest)
private int getNodeDepth(TreeNode root){
if(root==null) {return 0;
}else{
return Math.max(getNodeDepth(root.left),getNodeDepth(root.right))+1; }}}Copy the code257. All paths to a binary tree
The difficulty is simple
Given a binary tree, return all paths from the root node to the leaf node.
Note: Leaf nodes are nodes that have no child nodes.
Example:
Input: 1, 2, 3, 5 / output: [" 1 - > 2 - > 5 ", "1 - > 3"] : all the path of the root node to leaf node as follows: 1 - > 2 - > 5, 1 - > 3Copy the codeTrain of thought
This is depth-first, recursive:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList();
dfs(root,result,new ArrayList<Integer>());
return result;
}
private void dfs(TreeNode root,List<String> result,List<Integer> path){
if(root==null) {return;
}
path.add(root.val);
// Leaf node
if(root.left==null&&root.right==null) {int length = path.size();
StringBuffer sb = new StringBuffer();
for(int i = 0; i<length; i++){ sb.append(path.get(i));if(i! =length-1){
sb.append("- >");
}
}
result.add(sb.toString());
/ / back
path.remove(length-1);
return;
}
dfs(root.left,result,path);
dfs(root.right,result,path);
/ / back
path.remove(path.size()-1); }}Copy the code404. Sum of left leaves
Easy 280
Computes the sum of all left leaves of a given binary tree.
Example:
3 / \ 9 20 / \ 15 7 In this binary tree, there are two left leaves, 9 and 15, so return 24Copy the codeTrain of thought
First what is the left leaf: left node + leaf node
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
int sum =0;
public int sumOfLeftLeaves(TreeNode root) {
sum(root);
return sum;
}
private void sum(TreeNode root){
if(root==null) return;
if(root.left! =null) {The left node is the leaf node
if(root.left.left==null&&root.left.right==null){ sum =sum+root.left.val; } } sum(root.left); sum(root.right); }}Copy the code
Find the value in the lower left corner of the tree
Difficulty Medium 148
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input: 2 / \ 1 3 Output: 1Copy the codeExample 2:
Input: 1 / \ 2 3 / / \ 4 5 6/7 Output: 7Copy the codeNote: You can assume that the tree (that is, the given root node) is not NULL.
Train of thought
Record the leftmost sequence traversal directly:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
private int bottomLeftValue =0;
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque();
queue.add(root);
while(! queue.isEmpty()){int n = queue.size();
for(int i =0; i<n; i++){ TreeNode node = queue.poll();if(i==0){
bottomLeftValue=node.val;
}
if(node.left! =null){
queue.add(node.left);
}
if(node.right! =null){ queue.add(node.right); }}}returnbottomLeftValue; }}Copy the code112. Sum of paths
Simple difficulty 512
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: trueCopy the codeExample 2:
Input: root = [1,2,3], targetSum = 5 output: falseCopy the codeExample 3:
Input: root = [1,2], targetSum = 0 output: falseCopy the codeTip:
- The number of nodes in the tree is in the range
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Train of thought
This problem can also be done by backtracking, but it is important to note the definition of leaf nodes
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return false;
if(root.left==null&&root.right==null) {return targetSum==root.val;
}
returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val); }}Copy the code! [image-20210219225427781](/Users/frc/Library/Application Support/typora-user-images/image-20210219225427781.png)
113. Sum of paths II
Difficulty medium 425
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.
Note: Leaf nodes are nodes that have no child nodes.
Example: Given the following binary tree with the target and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Copy the codeReturns:
,4,11,2 [[5], [5,8,4,5]]Copy the codeTrain of thought
Since this case needs to record the path, there is a backtrace on the basis of recursion:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList();
if(root==null) return result;
backtracking(root,targetSum,new ArrayList<Integer>(),result);
return result;
}
private void backtracking(TreeNode root,int targetSum,List<Integer> path,List<List<Integer>> result){
if(root==null) {return;
}
path.add(root.val);
if(root.left==null&&root.right==null) {// Root is a leaf node
if(targetSum==root.val){
result.add(new ArrayList(path));
}
/ / back
path.remove(path.size()-1);
return ;
}else{
backtracking(root.left,targetSum-root.val,path,result);
backtracking(root.right,targetSum-root.val,path,result);
/ / back
path.remove(path.size()-1); }}}Copy the code