当前位置:网站首页>Li Kou Jianzhi offer -- binary tree chapter
Li Kou Jianzhi offer -- binary tree chapter
2022-07-05 01:39:00 【Blue and white porcelain secretly tapping code】
Preface
Hello everyone ! Long time no see. I'm blue and white porcelain , Did you brush the questions today ? List of articles , From easy to difficult , Step by step ,
This issue is a combination of Niuke 101 And the sword finger offer The above binary tree series OJ Interview questions
, Learning together , Progress together . If the solution is helpful to you , A little bit of praise to support , If there is something wrong , Welcome to correct
The series recommends ::
1. Basic operation of binary tree
2. First, middle and last traversal of binary tree ( Recursion and iteration )
3.【Java data structure 】 Binary tree, binary tree advanced —— Dachang classic OJ Interview questions —— Brush notes + How to do it
List of articles
Collection of brush questions of binary tree
Print binary tree
The finger of the sword Offer 32 - I. Print binary tree from top to bottom
OJ link : Print binary tree from top to bottom
Title Description :
Their thinking :
First read the meaning of the question , This problem is a Sequence traversal binary tree , But it needs to be returned to an array .
Specific steps :
- To borrow The order sheet Used to store the value of each node of the binary tree
- To borrow Secondary queue To complete the sequence traversal operation of binary tree
- Traverse The order sheet , Put the... Of each node in the order table It's worth going back to Array
The code is as follows :
class Solution {
public int[] levelOrder(TreeNode root) {
// Sequence traversal A line A sequence table
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> list = new ArrayList<>();
// If the header node is empty Return to one New array
if(root == null) return new int[0];
// If it's not empty Put the element Put in In line
queue.add(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
int[] ret = new int[list.size()];
for(int i = 0;i < list.size();i++) {
ret[i] = list.get(i);
}
return ret;
}
}
The finger of the sword Offer 32 - II. Print binary tree from top to bottom II
OJ link : Print binary tree from top to bottom II
Title Description :
Their thinking : This question is consistent with the previous one , Only this problem returns a two-dimensional array , In a nutshell , It's on the original one-dimensional array , Another layer of array is nested , This problem needs to pay attention to several details , as follows :
- Sequence traversal Indispensable auxiliary queue
- Return a two-dimensional array , We need a Two dimensional array receiving Return value
- Need to use A one-dimensional array first receives the value of each layer of nodes , Need here Be careful , Receive the value of each layer node , Need to be put into the loop , Ensure the number of values of each layer
- Specifically , Look at the code , Detailed notes
The code is as follows :
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// Sequence traversal Indispensable auxiliary queue
Queue<TreeNode> queue = new LinkedList<>();
// Returns a binary array
List<List<Integer>> ret = new ArrayList<>();
// Same , First determine whether the end node is empty
if(root == null) return ret;
// Not empty root Such as queue
queue.add(root);
// The loop condition
while(!queue.isEmpty()) {
// Because what we return is a two-dimensional array , Here we first use a one-dimensional array to receive the value of each node
List<Integer> list = new ArrayList<>();
// Here we want to guarantee , The value of each one-dimensional array , Here we need a layer of circulation
for(int i = queue.size();i > 0;i--) {
// eject queue Head Elements , use cur receive
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
// Cycle time , Put it once
ret.add(list);
}
// Finally, return a two-dimensional array
return ret;
}
}
The finger of the sword Offer 32 - III. Print binary tree from top to bottom III
OJ link : Print binary tree from top to bottom III
Title Description :
Their thinking :
Consistent with the above question , But this question says , Even layers , Print backwards , Here we need to do the following :
Because we The return is ret , Two dimensional array , therefore , We use it ret Size Go to % 2
, If == 0 , explain Even layers , conversely , Here we are use Double ended queue to receive For each floor Node values
The code is as follows :
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// This question is the same as the previous one , Just pay attention here :
// Even layers need to be printed backwards
// The difficulty here is : How to print in reverse , Here only need to be on the basis of the previous question
// Add a Judge if(ret % 2 == 0) The explanation is even , Then print in reverse
// Here print backwards , We directly use the properties of double ended queues , The bottom layer of the double ended queue is LinekdList, Linked list
// here Head insertion addLast Tail insertion addFirst
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ret = new ArrayList<>();
// If root == null return ret
if(root == null) return ret;
// Not empty Such as queue
queue.add(root);
// Into the loop
while(!queue.isEmpty()) {
// use List To receive Each layer The value of the node
LinkedList<Integer> tmp = new LinkedList<>();
// There are different layers ,list Received The number of nodes is different , So we enter the cycle
for(int i = queue.size();i > 0;i--) {
TreeNode cur = queue.poll();
// Join judgment , Judgment is Odd number layer still Even layers
if(ret.size() % 2 == 0) { // The description is an even number of layers , Print backwards , Head insertion
tmp.addLast(cur.val);
}else {
tmp.addFirst(cur.val);
}
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
ret.add(tmp);
}
return ret;
}
}
Search and backtracking algorithms
The finger of the sword Offer 26. The substructure of a tree
OJ link : The substructure of a tree
Title Description :
Their thinking && The code is as follows :
// This question , Mainly uses the nature of binary tree recursion
// The meaning of the title is given : If B yes A Of Substructure , Express A There are emergence and B Same structure and node value
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// The boundary conditions : If A perhaps B One of them is empty , Go straight back to false;
// Because the title gives , Empty numbers are not substructures of any number
if(A == null || B == null) return false;
// Judge the boundary , Next, it is divided into the following situations
// A and B The root node of is the same , Compare their child nodes in turn
// 1. A The root node and B The root node of is the same , Compare their child nodes in turn
// 2. A and B Of The root node is different , Judge A Whether in the left subtree of contain B The root node
// 3. A and B Of The root node is different , Judge A Whether in the right subtree of contain B The root node
return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
// The following methods , Realization A and B The root node is the same
boolean isSub(TreeNode A,TreeNode B) {
// 1. If the traversal is finished B, explain B All nodes of are and A On the substructure of
if(B == null) return true;
// 2. A The node in is null ,B The nodes in the Not empty , explain Mismatch
if(A == null) return false;
// 3. A and B It's not empty. , But the values are different , Description does not match
if(A.val != B.val) return false;
// Last , The current point is matched , Continue to recursively judge the left subtree and the right subtree , whether Each match
return isSub(A.left,B.left) && isSub(A.right,B.right);
}
}
The finger of the sword Offer 27. Image of binary tree
OJ link : Image of binary tree
Title Description :
Their thinking :
First analyze what the topic gives Input and output , Obviously , The input is based on the sequence traversal of the binary tree , Output... Let's see , Output graph , Except for the root node , The nodes of each layer are reversed .
Understand the meaning of the question , This problem is very simple , The specific steps are as follows :
- Sequence traversal binary tree
- After each stack , Exchange the values of the left and right nodes
- return The root node
The code is as follows :
class Solution {
public TreeNode mirrorTree(TreeNode root) {
// Sequence traversal
Queue<TreeNode> queue = new LinkedList<>();
// Be careful This question is different from the previous one , There is no need to return a binary array , One dimensional array or something , Just traverse normally
if(root == null) return null;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
// In exchange for
TreeNode tmp = cur.left;
cur.left = cur.right;
cur.right= tmp;
}
return root;
}
}
The finger of the sword Offer 28. Symmetric binary tree
OJ link : Symmetric binary tree
Title Description :
Their thinking :
According to the meaning , Symmetric binary tree , The specific steps are as follows :
- If The header node is empty return true, Empty numbers are also symmetric
- Judge Whether the left and right subtrees symmetry
- How to judge whether the left and right subtrees are symmetrical ? The specific code is as follows
The code is as follows :
class Solution {
public boolean isSymmetric(TreeNode root) {
// Termination conditions So is the blank number Symmetric binary tree
if(root == null) return true;
// If root It's not equal to empty return Auxiliary method
return func(root.left,root.right);
}
// Create methods , Judge Whether the left and right nodes are symmetrical
boolean func(TreeNode L,TreeNode R) {
// If Left and right nodes are empty return TRUE
if(L == null && R == null) return true;
// If One of the left and right nodes is empty , perhaps Around the node inequality
if(L == null || R == null) return false;
if(L.val != R.val) return false;
// Finally, recursive judgment L.left = R.right L.right = R.left
return func(L.left, R.right) && func(L.right, R.left);
}
}
Search and backtracking algorithms
The finger of the sword Offer 34. The path of a value in a binary tree
OJ link : The path of a value in a binary tree
Title Description :
Their thinking :
The code is as follows :
class Solution {
// DFS Depth-first search , use deque preservation route
// Return a two-dimensional array
Deque<Integer> path = new LinkedList<>();
List<List<Integer>> ret = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
DFS(root,target);
return ret;
}
public void DFS(TreeNode root,int target) {
// 1. If the header node is null, Go straight back to
if(root == null) return;
// 2. Not for null, Put in path in
path.add(root.val);
// 3. target Value minus root.val Value
target -= root.val;
// 4. If The root node is empty , also target == 0, That means we're done , Put the finished path into ret in
if(root.left == null && root.right == null && target == 0) {
// You can't just ret.add(path), If so ret Will follow path Change by change ,
// The operation here is to copy path
ret.add(new LinkedList<>(path));
}
// 5. If you are not satisfied , Continue to search
DFS(root.left,target);
DFS(root.right,target);
// 6. If Added value , Out of range
path.pollLast();
}
}
The finger of the sword Offer 36. Binary search tree and double linked list
OJ link : Binary search tree and double linked list
Title Description :
Their thinking && The code is as follows :
class Solution {
// According to the question : Binary search tree , The left node < The root node < Right node -》 In the sequence traversal
Node pre,head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
DFS(root);
// end to end
pre.right = head;
head.left = pre;
return head;
}
// DFS Search every node , And put each node Connected to a
public void DFS(Node cur) {
if(cur == null) return;
// In the sequence traversal
DFS(cur.left);
// Here we need to judge , If pre It's empty , explain head, Is the head node
if(pre == null) {
head = cur;
}else {
// If it's not empty , Building links
pre.right = cur;
}
cur.left = pre;
pre = cur;
DFS(cur.right);
}
}
The finger of the sword Offer 54. The second of binary search tree k Big node
OJ link : The second of binary search tree k Big node
Title Description :
Their thinking && The code is as follows :
class Solution {
// The core idea : Binary search tree , The middle order traversal is incremental
// So if we do the opposite It is decreasing , Prior to joining Counter , Not traversing a node counter ++
// Until the counter == k
// use ret receive Return value
int count;
int ret;
public int kthLargest(TreeNode root, int k) {
DFS(root,k);
return ret;
}
void DFS(TreeNode root,int k) {
if(root == null) return;
DFS(root.right,k);
count++;
if(count == k) ret = root.val;
DFS(root.left,k);
}
}
边栏推荐
- Global and Chinese markets for stratospheric UAV payloads 2022-2028: Research Report on technology, participants, trends, market size and share
- Introduction to the gtid mode of MySQL master-slave replication
- Yyds dry inventory swagger positioning problem ⽅ formula
- To sort out messy header files, I use include what you use
- Pytorch fine tuning (Fortune): hollowed out design or cheating
- Numpy library introductory tutorial: basic knowledge summary
- MATLB|多微电网及分布式能源交易
- Pytorch common code snippet collection
- Win:将一般用户添加到 Local Admins 组中
- Global and Chinese markets of emergency rescue vessels (errv) 2022-2028: Research Report on technology, participants, trends, market size and share
猜你喜欢
Redis(1)之Redis简介
微信小程序:全网独家小程序版本独立微信社群人脉
How to safely eat apples on the edge of a cliff? Deepmind & openai gives the answer of 3D security reinforcement learning
Redis master-slave replication cluster and recovery ideas for abnormal data loss # yyds dry goods inventory #
Incremental backup? db full
Yyds dry inventory swagger positioning problem ⽅ formula
[development of large e-commerce projects] performance pressure test - Performance Monitoring - heap memory and garbage collection -39
[swagger]-swagger learning
Win: use PowerShell to check the strength of wireless signal
Wechat applet: independent background with distribution function, Yuelao office blind box for making friends
随机推荐
PHP wechat official account development
MATLB | multi micro grid and distributed energy trading
R语言用logistic逻辑回归和AFRIMA、ARIMA时间序列模型预测世界人口
实战模拟│JWT 登录认证
Wechat applet: the latest WordPress black gold wallpaper wechat applet two open repair version source code download support traffic main revenue
I use these six code comparison tools
微信小程序;胡言乱语生成器
流批一体在京东的探索与实践
流批一體在京東的探索與實踐
"2022" is a must know web security interview question for job hopping
The perfect car for successful people: BMW X7! Superior performance, excellent comfort and safety
Outlook:总是提示输入用户密码
Express routing, express middleware, using express write interface
How to safely eat apples on the edge of a cliff? Deepmind & openai gives the answer of 3D security reinforcement learning
無心劍英譯席慕容《無怨的青春》
Wechat applet: wechat applet source code download new community system optimized version support agent member system function super high income
Pytorch fine tuning (Fortune): hollowed out design or cheating
Async/await you can use it, but do you know how to deal with errors?
What is the length of SHA512 hash string- What is the length of a hashed string with SHA512?
Discrete mathematics: reasoning rules