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)
traverse
Binary tree traversal can be divided into depth – first traversal and breadth – first traversal.
Often said: pre-order traversal, mid-order traversal, subsequent traversal is depth-first mode.
There are two ways of depth first: recursion and iteration.
Recursion: code is concise but spatial responsibility is high
Iteration: Space is saved, but Stack is used, so time is reduced
Depth first
Depth-first traversal is essentially a branch by branch traversal.
144. Antecedent traversal of binary trees
The difficulty is medium 513
Give you the root node of the binary tree, root, and return a pre-traversal of its node value.
Example 1:
Input: root = [1,null,2,3] output: [1, 3]Copy the codeExample 2:
Input: root = [] Output: []Copy the codeExample 3:
Input: root = [1] Output: [1]Copy the codeExample 4:
Input: root = [1,2] output: [2]Copy the codeExample 5:
Input: root = [1, NULL,2]Copy the codeTip:
- The number of nodes in the tree is in the range
[0, 100]内 -100 <= Node.val <= 100
Recursive writing
/** * 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<Integer> preorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList();
preorder(root,result);
return result;
}
private void preorder(TreeNode root,List<Integer> result){
if(root==null) return; result.add(root.val); preorder(root.left,result); preorder(root.right,result); }}Copy the code
The above time efficiency is very good, but the spatial complexity is very poor
The iterative method
/** * 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<Integer> preorderTraversal(TreeNode root) {
List<Integer> result= new ArrayList();
preorder(root,result);
return result;
}
private void preorder(TreeNode root,List<Integer> result){
Stack<TreeNode> stack =new Stack();
while(root! =null| |! stack.isEmpty()){while(root! =null){ result.add(root.val); stack.push(root); root=root.left; } TreeNode cur=stack.pop(); root=cur.right; }}}Copy the code145. Back-order traversal of binary trees
The difficulty is medium 521
Given a binary tree, return its backward traversal.
Example:
Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the codeAdvanced: The recursive algorithm is simple, can you do it with an iterative algorithm?
Recursive writing
/** * 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<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList();
postorder(root,result);
return result;
}
private void postorder(TreeNode root,List<Integer> result){
if(root==null)return; postorder(root.left,result); postorder(root.right,result); result.add(root.val); }}Copy the code
The iterative method
/** * 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<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(root! =null| |! stack.isEmpty()){while(root! =null){
result.add(root.val);
stack.push(root);
root = root.right;
}
TreeNode cur = stack.pop();
root = cur.left;
}
Collections.reverse(result);
returnresult; }}Copy the codeMiddle order traversal of binary trees
The difficulty is medium 858
Given the root node of a binary tree, return its middle-order traversal.
Example 1:
Input: root = [1,null,2,3]Copy the codeExample 2:
Input: root = [] Output: []Copy the codeExample 3:
Input: root = [1] Output: [1]Copy the codeExample 4:
Input: root = [1,2] output: [2,1]Copy the codeExample 5:
Input: root = [1, NULL,2]Copy the codeTip:
- The number of nodes in the tree is in the range
[0, 100]内 -100 <= Node.val <= 100
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<Integer> inorderTraversal(TreeNode root) {
List<Integer> result= new ArrayList();
inorder(root,result);
return result;
}
private void inorder(TreeNode root,List<Integer> result){
if(root==null)return; inorder(root.left,result); result.add(root.val); inorder(root.right,result); }}Copy the code
The iteration
The iterative writing method of middle order traversal is a little different from the previous two, mainly when recording parameters.
/** * 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<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList();
Stack<TreeNode> stack = new Stack();
while(root! =null| |! stack.isEmpty()){while(root! =null){
stack.push(root);
root = root.left;
}
root = stack.pop();
result.add(root.val);
root = root.right;
}
returnresult; }}Copy the code
breadth-first
In binary trees, breadth first is actually traversal layer by layer, that is, sequence traversal.
This article is the solution of LeetCode, feel about the sequence traversal said quite well
Breadth-first leverages the first-in, first-out nature of queues. The template is as follows:
void bfs(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);/ / the root node
while(! queue.isEmpty()) { TreeNode node = queue.poll();// Retrieve the Node that was entered first
if(node.left ! =null) {
queue.add(node.left);
}
if(node.right ! =null) { queue.add(node.right); }}}Copy the code102. Sequence traversal of binary trees
The difficulty is medium 773
Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).
Example: binary tree: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Copy the codeReturn the sequence traversal result:
[[3], [9,20], [15,7]Copy the code/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result =new ArrayList();
// Double-endian queue
Queue<TreeNode> queue = new ArrayDeque();
if(root! =null){
queue.add(root);
}
while(! queue.isEmpty()){// Record the data for each layer
List<Integer> level = new ArrayList();
// The width of the current layer
int N = queue.size();
for(int i = 0; i < N; i++){// Fetch the first Node
TreeNode node =queue.poll();
level.add(node.val);
if(node.left! =null){
queue.add(node.left);
}
if(node.right! =null){
queue.add(node.right);
}
}
result.add(level);
}
returnresult; }}Copy the code
107. Sequence traversal of binary trees II
Easy difficulty 405
Given a binary tree, return a bottom-up traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)
For example, given a binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Copy the codeReturn its bottom-up sequence traversal as:
[[15,7], [9,20], [3]Copy the codeThe result returned in reverse order is the result returned in reverse order.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList();
Queue<TreeNode> deque = new ArrayDeque();
if(root! =null){
deque.add(root);
}
while(! deque.isEmpty()){ List<Integer> level =new ArrayList();
int n =deque.size();
for(int i = 0; i < n; i++){
TreeNode node =deque.poll();
level.add(node.val);
if(node.left! =null){
deque.add(node.left);
}
if(node.right! =null){ deque.add(node.right); }}// The top layer is sorted in the following order.
result.add(0,level);
}
returnresult; }}Copy the code199. Right view of binary trees
Difficulty medium 405
Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right side, in order from top to bottom.
Example:
Input: [5, 1, 2, 3, null, null, 4] output: [1, 3, 4] explanation: < 1-2 3 < / \ - \ \ 5 4 < -- -- -Copy the codeNote only the last element of each line:
/** * 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<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList();
Queue<TreeNode> deQueue = new ArrayDeque();
if(root! =null){
deQueue.add(root);
}
while(! deQueue.isEmpty()){int n = deQueue.size();
for(int i = 0; i < n; i++){
TreeNode node = deQueue.poll();
if(i==n-1) {// Just record the last one in the line
result.add(node.val);
}
if(node.left! =null){
deQueue.add(node.left);
}
if(node.right! =null){ deQueue.add(node.right); }}}returnresult; }}Copy the code637. Mean level of binary trees
The Difficulty is simple 236
Given a non-empty binary tree, return an array of the average values of nodes at each level.
Example 1:
Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average of level 0 is 3, level 1 is 14.5 and level 2 is 11. So return [3, 14.5, 11].Copy the codeTip:
- The node values are in the range of 32 – bit signed integers.
The local difference is to get the sum for each row and then get the average
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList();
Queue<TreeNode> deQueue = new ArrayDeque();
if(root! =null){
deQueue.add(root);
}
while(! deQueue.isEmpty()){int n = deQueue.size();
// Notice the use of the Double type
Double levelSum =0.0;
for(int i = 0; i < n; i++){
TreeNode node = deQueue.poll();
/ / add
levelSum=levelSum+node.val;
if(node.left! =null){
deQueue.add(node.left);
}
if(node.right! =null){
deQueue.add(node.right);
}
}
result.add(levelSum/n);
}
returnresult; }}Copy the code429. Sequence traversal of N fork tree
Difficulty medium 130
Given an n-tree, return a sequential traversal of its node values. (that is, from left to right, layer by layer).
The serialized input to the tree is traversed in order, with each set of child nodes separated by null values (see example).
Example 1:
Input: root = [1, null, 3 4-trichlorobenzene, null, 5, 6] output: [[1], [3, 4-trichlorobenzene], [5, 6]]Copy 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: [[1], [2, 5-tetrafluorobenzoic],,7,8,9,10 [6], [11], [14]]Copy the codeTip:
- The height of the tree cannot exceed
1000 - The total number of nodes in the tree is
[0, 10 ^ 4)between
Subject to102. Sequence traversal of binary treesThe difference is that there may currently be N nodes under each Node.
/* // 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 {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result =new ArrayList();
// Double-endian queue
Queue<Node> queue = new ArrayDeque();
if(root! =null){
queue.add(root);
}
while(! queue.isEmpty()){// Record the data for each layer
List<Integer> level = new ArrayList();
// The width of the current layer
int N = queue.size();
for(int i = 0; i < N; i++){// Fetch the first Node
Node node =queue.poll();
level.add(node.val);
/ / N nodes
for(Node child : node.children){
queue.add(child);
}
}
result.add(level);
}
returnresult; }}Copy the codeLook for the maximum value in each tree line
Difficulty medium 124
You need to find the maximum value in each row of the binary tree.
Example:
Input: 1 / \ 3 2 / \ 5 3 9 Output: [1, 3, 9]Copy the codeSubject to637. Mean level of binary treesIt’s basically the same thing, one for the maximum, one for the average
/** * 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<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList();
Queue<TreeNode> deQueue = new ArrayDeque();
if(root! =null){
deQueue.add(root);
}
while(! deQueue.isEmpty()){int n = deQueue.size();
// The maximum value of the current layer, Node can be negative, so this cannot be 0
Integer levelMax = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
TreeNode node = deQueue.poll();
// Get a larger value
levelMax=Math.max(node.val,levelMax);
if(node.left! =null){
deQueue.add(node.left);
}
if(node.right! =null){
deQueue.add(node.right);
}
}
result.add(levelMax);
}
returnresult; }}Copy the code116. Populate the next right node pointer for each node
Difficulty Medium 395
Given a perfect binary tree, all leaf nodes are at the same level and each parent node has two children. Binary trees are defined as follows:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Copy the codePopulate each of its next Pointers to point to its next right-hand node. If the next right-side node cannot be found, set the next pointer to NULL.
Initially, all next Pointers are set to NULL.
Advanced:
-
You can only use constant level extra space.
-
Using recursion is also acceptable, in this case the stack space occupied by the recursive program does not count as additional space complexity.
Example:
Explanation: Given A binary tree as shown in Figure A, your function should fill each of its next Pointers to point to its next node on the right, as shown in Figure B. The serialized outputs are traversed in order, with nodes of the same layer connected by the next pointer, '#' marking the end of each layer.Copy the codeTip:
- The number of nodes in the tree is less than
4096 -1000 <= node.val <= 1000
/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; }}; * /
class Solution {
public Node connect(Node root) {
// We need to record the root node
Node connectedNode=root;
Queue<Node> queue = new ArrayDeque();
if(root! =null){
queue.add(root);
}
while(! queue.isEmpty()){// The width of the current layer
int N = queue.size();
for(int i = 0; i < N; i++){// Fetch the first Node
Node node=queue.poll();
// Not the last element of each line,
if(i<N-1) {// Peek () is used here
node.next=queue.peek();
}
if(node.left! =null){
queue.add(node.left);
}
if(node.right! =null){ queue.add(node.right); }}}returnconnectedNode; }}Copy the code117. Populate the next right node pointer II for each node
This problem is the same as the last one. Even though the previous problem was a complete binary tree, the solution to the previous problem didn’t even have to worry about whether it was a complete binary tree.