LeetCode - Easy - 226. Invert Binary Tree

阳光穿透心脏的1/2处 2022-12-31 06:26 140阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/invert-binary-tree/][https_leetcode.com_problems_invert-binary-tree]

Invert a binary tree.

**Example**:

Input:

4
       /   \
      2     7
     / \   / \
    1   3 6   9

Output:

4
       /   \
      7     2
     / \   / \
    9   6 3   1

**Trivia**:  
This problem was inspired by this original tweet by Max Howell:

> Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f\*\*\* off.

## Analysis ##

方法一：递归（DFS）

方法二：迭代（DFS）

方法三：迭代（BFS）

## Submission ##

import java.util.LinkedList;
    import java.util.Queue;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class InvertBinaryTree { 
    
    	// 方法一：递归（DFS）
    	public TreeNode invertTree1(TreeNode root) { 
    		if (root == null)
    			return null;
    		TreeNode temp = invertTree1(root.left);
    		root.left = invertTree1(root.right);
    		root.right = temp;
    		return root;
    	}
    
    	// 方法二：迭代（DFS）
    	public TreeNode invertTree2(TreeNode root) { 
    		if (root == null)
    			return null;
    
    		LinkedList<TreeNode> stack = new LinkedList<>();
    		stack.push(root);
    
    		while (!stack.isEmpty()) { 
    			TreeNode node = stack.pop();
    			TreeNode left = node.left;
    			node.left = node.right;
    			node.right = left;
    
    			if (node.left != null)
    				stack.push(node.left);
    
    			if (node.right != null)
    				stack.push(node.right);
    		}
    		return root;
    	}
    
    	// 方法三：迭代（BFS）
    	public TreeNode invertTree3(TreeNode root) { 
    		if (root == null)
    			return null;
    
    		Queue<TreeNode> queue = new LinkedList<>();
    		queue.offer(root);
    
    		while (!queue.isEmpty()) { 
    			TreeNode node = queue.poll();
    			TreeNode left = node.left;
    			node.left = node.right;
    			node.right = left;
    
    			if (node.left != null)
    				queue.offer(node.left);
    
    			if (node.right != null)
    				queue.offer(node.right);
    		}
    		return root;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class InvertBinaryTreeTest { 
    
    	@Test
    	public void test1() { 
    		InvertBinaryTree obj = new InvertBinaryTree();
    		TreeNode root = makeATree();
    		TreeNode expected = makeExpectedTree();
    		assertTrue(BinaryTree.equals(obj.invertTree1(root), expected));
    	}
    
    	@Test
    	public void test2() { 
    		InvertBinaryTree obj = new InvertBinaryTree();
    		TreeNode root = makeATree();
    		TreeNode expected = makeExpectedTree();
    		assertTrue(BinaryTree.equals(obj.invertTree2(root), expected));
    	}
    
    	@Test
    	public void test3() { 
    		InvertBinaryTree obj = new InvertBinaryTree();
    		TreeNode root = makeATree();
    		TreeNode expected = makeExpectedTree();
    		assertTrue(BinaryTree.equals(obj.invertTree3(root), expected));
    	}
    	
    	private TreeNode makeATree() { 
    		return new TreeNode(4,//
    				new TreeNode(2,//
    					new TreeNode(1),//
    					new TreeNode(3)),//
    				new TreeNode(7, //
    					new TreeNode(6),//
    					new TreeNode(9)));
    	}
    	
    	private TreeNode makeExpectedTree() { 
    		return new TreeNode(4, //
    				new TreeNode(7, //
    					new TreeNode(9), //
    					new TreeNode(6)), //
    				new TreeNode(2,  //
    					new TreeNode(3), //
    					new TreeNode(1)));
    	}
    }

[https_leetcode.com_problems_invert-binary-tree]: https://leetcode.com/problems/invert-binary-tree/