翻转二叉树

翻转二叉树

问题

这个题目说的是，给你一棵二叉树，你要把它左右镜像翻转，然后返回翻转后的二叉树。

比如说，给你的二叉树是：

     1
   /   \
  2     4
       / \
      8  16

左右翻转后的二叉树是：

      1
    /   \
   4     2
  / \
 16  8

我们可以看到，二叉树上所有节点都沿中轴线左右互换了位置

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public TreeNode invertBinaryTreeRecursive(TreeNode root) {
    if (root == null) return root;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertBinaryTreeRecursive(root.left);
    invertBinaryTreeRecursive(root.right);
    return root;
  }

  // Time: O(n), Space: O(n)
  public  TreeNode invertBinaryTreeIterative(TreeNode root) {
    if (root == null) return root;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      TreeNode node = q.poll();
      TreeNode tmp = node.left;
      node.left = node.right;
      node.right = tmp;
      if (node.left != null) q.add(node.left);
      if (node.right != null) q.add(node.right);
    }
    return root;
  }

}