<> Core test site : Binary tree operation

Operate the given binary tree , Transform it into a mirror of the source binary tree .

analysis :
To change a binary tree into its own image , Just exchange the left and right subtrees of each node of the binary tree .

for example , After we exchange the left and right subtrees of the root node of the above binary tree, the source binary tree will change as follows .

Then continue to exchange the left and right subtrees of the nodes of the next layer , You can get the binary tree mirrored by the source binary tree .

But in fact, we also exchange the left and right subtrees of leaf nodes , However, the left and right subtrees of leaf nodes are empty trees, and the binary tree does not change after exchange .

Binary trees are recursively defined , Therefore, recursive operation is a common practice .
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };*/ class Solution {
public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr) // Empty trees do not require mirroring
return nullptr; TreeNode* left = Mirror(pRoot->left); // Mirror the left subtree of the node TreeNode*
right= Mirror(pRoot->right); // Mirror the right subtree of this node // Exchange the left and right subtrees of the node pRoot->left = right;
pRoot->right = left; return pRoot; // Return to this node } };
However, we only need to exchange the left and right subtrees of all nodes of the binary tree , So we can use any method that can traverse a binary tree , The following shows the solution using queue and stack .

Use the queue to traverse the binary tree to exchange the left and right subtrees of each node .
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };*/ class Solution {
public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr) // Empty trees do not require mirroring
return nullptr; queue<TreeNode*> q; q.push(pRoot); // Put the root node into the queue first while (!q.empty())
{ // Take team head node TreeNode* pNode = q.front(); q.pop(); // Exchange the left and right subtrees of the node TreeNode* temp =
pNode->left; pNode->left = pNode->right; pNode->right = temp;
// If the left node of this node is not empty , The left node is queued if (pNode->left) q.push(pNode->left);
// If the right node of this node is not empty , The right node is queued if (pNode->right) q.push(pNode->right); } return pRoot;
// Return root node } };
Use the stack to traverse the binary tree to exchange the left and right subtrees of each node .
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };*/ }; class
Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (pRoot == nullptr)
// Empty trees do not require mirroring return nullptr; stack<TreeNode*> st; st.push(pRoot); // Put the root node on the stack first while (!
st.empty()) { // Stack top node TreeNode* pNode = st.top(); st.pop(); // Exchange the left and right subtrees of the node
TreeNode* temp = pNode->left; pNode->left = pNode->right; pNode->right = temp;
// If the left node of this node is not empty , Then put its left node on the stack if (pNode->left) st.push(pNode->left);
// If the right node of this node is not empty , Then put its right node on the stack if (pNode->right) st.push(pNode->right); } return pRoot;
// Return root node } };

Technology
©2019-2020 Toolsou All rights reserved,
Android Using wechat in H5 Payment result refresh during payment shock !!C++ Can make a sound ! Basic operation of single linked list C Language explanation Java Implement an epidemic number management system 2021 year 11 World programming language ranking linux upper mysql Invalid command _linux lower mysql The command is useless Java project : Campus dormitory management system (java+jsp+javaweb+mysql+ajax) Wechat applet development project directory linux ubuntu Which version ,Ubuntu Which version is the best ?python Code painting cherry blossoms - How to use Python Draw a beautiful cherry blossom