LeetCode - Easy - 226. Invert Binary Tree-蒲公英云

LeetCode - Easy - 226. Invert Binary Tree

Topic

Tree

Description

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)));
    }
}