LeetCode226. Flip binary tree

LeetCode226. Flip binary tree

1. problem

2. Ideas

The overall idea is to flip the left and right children of each node , So we need to traverse the binary tree . The focus is on how to traverse the binary tree ！

Before the order 、 In the following order 、 Sequence is OK , No middle order , Because some nodes will be exchanged twice ！

The next preface is an example ：

3. Code implementation

（1） recursive

class Solution {
    
public:
    TreeNode* invertTree(TreeNode* root) {
    
    //1. Termination conditions 
        if(root==NULL) return NULL;
    //2. Exchange left and right nodes 
        TreeNode* tmp=root->left;
        root->left=root->right;
        root->right=tmp;
    //3. Traverse the left and right subtrees 
        invertTree(root->left);
        invertTree(root->right);	
        return root; 
    }
};

Be careful ：

The code of the exchange node is ：
TreeNode* tmp=root->left; root->left=root->right; root->right=tmp;
Or use swap function ！！！

swap(root->left, root->right);

Error code ：

This is wrong ！
Only the values of some two nodes are exchanged , Without completely inverting the entire subtree ！
TreeNode *tmpNode = new TreeNode();// Create a new node
tmpNode->val = root->right->val;// Exchange value
root->right->val = root->left->val;
root->left->val = tmpNode->val;
For example, the first step is completed , It becomes as shown in the figure below ：

（2） iteration

class Solution {
    
public:
   TreeNode* invertTree(TreeNode* root) {
    
    stack<TreeNode*>st;
    if(root == NULL) return root;
   	st.push(root);// The root node is in the stack ！
    while(!st.empty())// Stack is not empty  
    {
    
    	TreeNode* node = st.top();// The pointer points to the top node of the stack  // in  
    	st.pop();// Out of the stack  
        swap(node->left, node->right);
    	if(node->right) st.push(node->right);// The right son enters the stack ！( Empty nodes do not stack ) 
    	if(node->left)  st.push(node->left);// Left son into the stack ！（ Empty nodes do not stack ） 
	}
	return root; // The stack is empty. , end  
	}
};