#226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

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

输出：

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

备注：

这个问题是受到Max Howell的原问题启发的：

谷歌：我们 90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package xyz.onns.leetcode;

/**
 * @Author Onns
 * @Date 2020/9/16 9:41 AM
 * @Version 1.0
 * @Website https://onns.xyz/blog/
 */
public class InvertBinaryTree {
	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 * int val;
	 * TreeNode left;
	 * TreeNode right;
	 * TreeNode(int x) { val = x; }
	 * }
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

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

	class Solution {
		public TreeNode invertTree(TreeNode root) {
			if (root == null) return root;
			exchange(root);
			return root;
		}

		void exchange(TreeNode root) {


			TreeNode t = root.left;
			root.left = root.right;
			root.right = t;
			if (root.left != null) {
				exchange(root.left);
			}
			if (root.right != null) {
				exchange(root.right);
			}
		}
	}
}