leetcode:226. Flip binary tree

226. Flip binary tree

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/invert-binary-tree/

Give you the root node of a binary tree root , Flip this binary tree , And return its root node .

Example 1：

 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 ：[]

Tips ：

• The number of nodes in the tree ranges from [0, 100] Inside
• -100 <= Node.val <= 100

solution

• recursive ： Start at the root node , Swap two child nodes , Then recursively process the two child nodes
• bfs loop : Use a queue to store the nodes of each tier , Then each time from the queue header pop Let's get a node , Swap the child nodes of this node , If the child node is not empty , Add child nodes to the queue ;

Code implementation

recursive

python Realization

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        #  Recursion end condition 
        if not root or (not root.left and not root.right):
            return root
        #  Process this node 
        root.left, root.right = root.right, root.left
        #  Recursive next node 
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    TreeNode* invertTree(TreeNode* root) {
    
        if (root == nullptr || (root->left == nullptr && root->right == nullptr))
            return root;
        
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;

        if (root->left != nullptr)
            invertTree(root->left);
        
        if (root->right != nullptr)
            invertTree(root->right);
        
        return root;
    }
};

Complexity analysis

• Time complexity ： $O(N)$
• Spatial complexity ： $O(N)$ The space used is determined by the depth of the recursive stack , It is equal to the height of the current node in the binary tree . On average , The height of a binary tree has a logarithmic relationship with the number of nodes , namely $O(logN)$ . And in the worst case , Trees form chains , The space complexity is $O(N)$.

BFS loop

python Realization

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root or (not root.left and not root.right):
            return root
        
        stack = [root]
        while stack:
            node = stack.pop(0)
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root 

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    TreeNode* invertTree(TreeNode* root) {
    
        if (root == nullptr || (root->left == nullptr && root->right == nullptr))
            return root;
        
        queue<TreeNode*> qs;
        qs.push(root);
        TreeNode *tmp;
        while(qs.size() > 0) {
    
            tmp = qs.front();
            qs.pop();
            TreeNode * tmp2 = tmp->left;
            tmp->left = tmp->right;
            tmp->right = tmp2;

            if (tmp->left != nullptr)
                invertTree(tmp->left);
            if (tmp->right != nullptr)
                invertTree(tmp->right);
        }
        return root;
    }
};

Complexity analysis

• Time complexity ： $O(N)$
• Spatial complexity ： $O(N)$