Binary tree - 226. Flip binary tree

1 Title Description

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

2 Title Example

Example 3：

Input ：root = []
Output ：[]

3 Topic tips

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

4 Ideas

recursive ：
This is a classic binary tree problem . obviously , We start at the root node , Recursively traverse the tree , And start flipping from the leaf node . If the node currently traversed root The two subtrees on the left and right have been turned over , Then we just need to exchange the positions of the two subtrees , Can be completed to root Is the flip of the entire subtree of the root node .
Complexity analysis
Time complexity :o(N), among N Is the number of binary tree nodes . We will traverse every node in the binary tree , For each node , We exchange its two subtrees in constant time .
· 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(log N). And in the worst case , Trees form chains , The space complexity is O(N).

iteration ：

Recursive implementation is the way of depth first traversal , So the corresponding is breadth first traversal .
Breadth first traversal requires additional data structures – queue , To store the temporarily traversed elements .
Depth first traversal is characterized by a rod inserted to the end , No, go back and continue ; The characteristic of breadth first traversal is sweeping at all levels .
therefore , We need to put the root node in the queue first , Then iterate over the elements in the queue .
Swap the positions of the left and right subtrees of the current element , then :
Judge whether the left subtree is empty , If it is not empty, put it into the queue to judge whether its right subtree is empty , If it is not empty, it will be put into the queue
Time complexity : Similarly, each node needs to be queued / Outgoing queue — Time , So it is o(n)
Spatial complexity : In the worst case, all leaf nodes will be included , The leaf nodes of a complete binary tree are n/2 individual , So time complexity is 0(n)

5 My answer

recursive ：

class Solution {
    
    public TreeNode invertTree(TreeNode root) {
    
        if (root == null) {
    
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

iteration ：

class Solution {
    
	public TreeNode invertTree(TreeNode root) {
    
		if(root==null) {
    
			return null;
		}
		// Put the nodes in the binary tree into the queue layer by layer , Then iterate over the elements in the queue 
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while(!queue.isEmpty()) {
    
			// Take a node from the queue each time , And exchange the left and right subtrees of this node 
			TreeNode tmp = queue.poll();
			TreeNode left = tmp.left;
			tmp.left = tmp.right;
			tmp.right = left;
			// If the left subtree of the current node is not empty , Then put it into the queue for subsequent processing 
			if(tmp.left!=null) {
    
				queue.add(tmp.left);
			}
			// If the right subtree of the current node is not empty , Then put it into the queue for subsequent processing 
			if(tmp.right!=null) {
    
				queue.add(tmp.right);
			}
			
		}
		// Return the processed root node 
		return root;
	}
}