LeetCode topic link:/problems/invert-binary-tree/
Title Narrative:
Given the root node of a binary tree, flip the binary tree and return its root node.
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
reasoning
This question in fact, we only need to reverse each node left subtree and right subtree can be used, you can use the recursive method and iterative method, in the following I will explain, the recursive method is that we have a problem, it will be abstracted into a finite number of sub-problems, and then use the same method to deal with these sub-problems on the line
We don't think about the process of recursion, we just need to deal with the boundaries of the recursion and the processing conditions, so that the recursion we write is sure to be right.
The core of dealing with recursion is to never think about the subproblem process, how many layers can your brain handle? You'll get confused right away. Think about the result of the subproblem, and your mind will be clear!
As long as the logic of the boundary conditions and non-boundary conditions of the code is written correctly, the rest is left to mathematical induction. That is, write the right logic for both and your code is automatically correct, there's no need to think about how recursion goes layer by layer.
Ideas extended to all binary tree topics
- How to think about binary tree related problems?
- Don't get bogged down in the details right off the bat, but think about the whole tree in relation to its left and right subtrees.
- Why do I need to use recursion?
- The subproblems are similar to the original problem and they execute the same code (analogous to loops), but the subproblems need to return the result of the computation to the higher level, which is more suitable to be implemented with recursion.
- Why does writing it this way make it certain that the correct answer will be calculated?
- Because the size of the subproblem than the original problem is small, continue to "recursive", there will always be an end, that is, the recursive boundary conditions ( base case ), and return directly to its answer "return";
- Similar to mathematical induction (dominoes), similar to boundary conditions when n=1; similar to any node backward when n=m
- How does a computer perform recursion?
- When the program executes the "pass" action, the computer uses the stack to save the object that issued the "pass" action, the program continues to "pass", the computer continues to press the stack until the boundary when the program The "return" action occurs, just the answer to the implementation of the "return" to the top element of the stack, and then the program continues to "return", the computer continues to go out of the stack until the return of the answer to the original question, the stack is empty.
- Another recursive idea
- Maintains global variables, using a binary tree traversal function that constantly updates the maximum value of the global variable.
recursive method
Recursive method using preorder traversal and postorder traversal is OK, but use the middle order traversal should be careful, because the middle order traversal, you deal with the order of the nodes is the left in the right, it proves that you have dealt with the left sub-tree, the left sub-tree has been inverted once, if you flip the right sub-tree at this time, is the
There's another flip to the original left subtree, so that's something we have to be aware of!
preorder traversal
//Pre-order traversal of a flipped binary tree
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
backward traversal
//Posterior order traversal of a flipped binary tree
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};
medium-order traversal
// Middle-order traversal of a flip-flop binary tree
class Solution {
public.
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root; //Flip the left child tree.
// Flip the left subtree
invertTree(root->left);
swap(root->left, root->right);
// Note here! Since we have already flipped the left subtree once, here we want to flip the original left subtree, we still need to manipulate the "left subtree"
invertTree(root->left).
return root.
}
}; }
iterative method
Iterative methods we use preorder, postorder, and cascade traversal are all possible, and in the following I'll describe all three:
preorder traversal
//Precedence Traversal Iteration Method for Flipping Binary Trees
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
stack<TreeNode*> st;
(root);
while (!()) {
TreeNode* current = ();
();
swap(current->left, current->right);
if (current->right != NULL) (current->right);
if (current->left != NULL) (current->left);
}
return root;
}
};
Layer-order traversal:
//Hierarchical Traversal Iteration Method for Flipping Binary Trees
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
queue<TreeNode*> que;
(root);
while (!()) {
int size = ();
while (size--) {
TreeNode* current = ();
();
swap(current->left, current->right);
if (current->left != NULL) (current->left);
if (current->right != NULL) (current->right);
}
}
return root;
}
};
backward traversal
// Posterior traversal iteration method to flip a binary tree
class Solution {
public.
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root; stack<TreeNode*&g
stack<TreeNode*> st.
(root);
while (! ()) {
TreeNode* current = ();
();
swap(current->left, current->right);
// The only difference from a preorder traversal is that the left subtree is processed first, which is not actually called a postorder traversal, the actual traversal order is center-right-left!
if (current->left ! = NULL) (current->left).
if (current->right ! = NULL) (current->right);
}
current->right); }
}
}; }