P47 翻转二叉树

描述#

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

比如说，给你的二叉树是：
 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;
  }

}