Without further ado, just shout a slogan to encourage yourself: Programmers will never be unemployed, programmers go to architecture! The theme of this blog is [morphological changes of binary trees], which is implemented using the basic data structure [binary tree]. The website for this high-frequency question is: CodeTop, and the filtering conditions are: Target company + Last year + Sort by frequency of occurrence, from high to low, go to Nuke TOP101 to find, there are only two Do this question only after it has appeared in various places (CodeTop itself gathers the sources of LeetCode), and make sure that the questions you answer are all frequently asked for interviews.
After the title of the famous track, attach a link to the question. Later, you can practice quickly and repeatedly based on the problem-solving ideas.The questions are classified according to the basic data structure of the question stem, and the first of each category This article must be an introduction to basic data structures.
Symmetric binary tree [EASY]
Judgment of symmetric binary tree
Question stem
Problem-solving ideas
Symmetry means that the left and right sides are equal, that is, the left subtree and the right subtree are equivalent. Pay attention to this sentence, the left subtree and the right subtree are equal, which means that the left subtree and the right subtree must be compared recursively.
We call the left subtree of the root node left and the right subtree right.
- Compare whether left is equal to right. If not, just return it directly.
- If they are equal, compare the left node of left with the right node of right, and then compare the right node of left with the left node of right
For example, look at the following two subtrees (they are the left subtree and right subtree of the root node respectively), you can observe such a pattern
- Termination condition: When the two nodes entering the sub-problem are both empty, it means that they have reached the leaf nodes and are synchronized, so the sub-problem ends and true is returned; when the two nodes entering the sub-problem are empty Only one node is empty, or the element values are unequal, indicating that the symmetry here does not match. This sub-problem is also ended and false is returned.
- Return value: Each level passes the result of whether the sub-question matches up.
- Tasks at this level: Each sub-problem needs to follow the above ideas. When the “root left” goes to the left, the “root right left” goes to the right. When the “root left and right” goes to the right, the “root right left” goes to the left. Entering the sub-problem together requires matching on both sides to be symmetrical
Code implementation
Give the code to implement the basic file
Basic data structure: Binary tree
Auxiliary data structure: None
Algorithm: Recursion, DFS
Tips: None
The data structures, algorithms and techniques come from:
- 10 data structures: Array, linked list, stack, queue, hash table, binary tree, heap, skip list, graph, Trie tree
- 10 algorithms: Recursion, sorting, binary search, search, hash algorithm, greedy algorithm, divide and conquer algorithm, backtracking algorithm, dynamic programming, string matching algorithm
- Techniques: Dual pointers, sliding window, center diffusion
Of course including but not limited to the above
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
*TreeNode left = null;
*TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {<!-- -->
/**
* The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
*
*
* @param pRoot TreeNode class
* @return bool Boolean type
*/
public boolean isSymmetrical (TreeNode pRoot) {<!-- -->
if (pRoot == null) {<!-- -->
return true;
}
return dfsCheck(pRoot.left, pRoot.right);
}
private boolean dfsCheck(TreeNode left, TreeNode right) {<!-- -->
// 1 Recursive termination condition: If the left and right child nodes are both null, it means that the leaf node is reached, terminated and true
if (left == null & amp; & amp; right == null) {<!-- -->
return true;
}
// 2 Judgment basis at this level: If one of the two nodes is null, it is asymmetrical
if (left == null || right == null) {<!-- -->
return false;
}
// 3 Judgment basis at this level: If the two node values are not equal, it is asymmetrical
if (left.val != right.val) {<!-- -->
return false;
}
// 4 Continue to enter the lower level to make judgments
return dfsCheck(left.right, right.left) & amp; & amp; dfsCheck(left.left, right.right);
}
}
Complexity analysis
Time complexity: O(n), where n is the number of nodes in the binary tree, traversing the entire binary tree
Space complexity: O(n), in the worst case, the binary tree is transformed into a linked list, and the maximum depth of the recursive stack is n
Flip Binary Tree【EASY】
Similar to a symmetric binary tree, except that the symmetric binary tree is a judgment, and the flipped binary tree is a node displacement.
Question stem
Problem-solving ideas
In fact, it is to exchange the left and right nodes, and then recursively exchange the left node. We can summarize the two conditions of recursion for the right node as follows:
- Termination condition: Returned when the current node is null
- Exchange the left and right nodes of the current node, then recursively exchange the left node of the current node, and recursively exchange the right node of the current node
Depth first traversal.
Code implementation
Give the code to implement the basic file
Basic data structure: Binary tree
Auxiliary data structure: None
Algorithm: Recursive, DFS
Tips: None
The data structures, algorithms and techniques come from:
- 10 data structures: Array, linked list, stack, queue, hash table, binary tree, heap, skip list, graph, Trie tree
- 10 algorithms: Recursion, sorting, binary search, search, hash algorithm, greedy algorithm, divide and conquer algorithm, backtracking algorithm, dynamic programming, string matching algorithm
- Techniques: Dual pointers, sliding window, center diffusion
Of course including but not limited to the above
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
*TreeNode left = null;
*TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {<!-- -->
/**
* The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
*
*
* @param pRoot TreeNode class
* @return TreeNode class
*/
public TreeNode Mirror (TreeNode pRoot) {<!-- -->
if (pRoot == null) {<!-- -->
return null;
}
dfsChange(pRoot);
return pRoot;
}
private TreeNode dfsChange(TreeNode node) {<!-- -->
// 1 Recursion termination condition: node is null
if (node == null) {<!-- -->
return null;
}
// 2 Tasks at this level, exchange the left and right subtrees
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// 3 Recursively exchange the internal structure of the left and right subtrees
dfsChange(node.left);
dfsChange(node.right);
return node;
}
}
Complexity analysis
Time complexity: The entire tree node is traversed, the time complexity is O(N)
Space complexity: In extreme cases, the binary tree degenerates into a linked list, the depth of the recursive stack is O(N), and the space complexity is O(N)