LintCode 175. Invert Binary Tree 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/invert-binary-tree/
Invert a binary tree.
Example
1 1
/ \ / \
2 3 => 3 2
/ \
4 4
解题思路
题目是反转二叉树。
分治法。反转左子树，反转右子树。对调根节点左右子树。
这道题有个趣味故事。Mac OS上的非常著名的软件Homebrew作者在Google面试时竟然做不出这道题，并且最终被拒绝。
Google：我们 90% 的工程师都用你写的软件（Homebrew），但你没法在白板上翻转二叉树，所以滚蛋吧。
参考代码
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void invertBinaryTree(TreeNode root) {
if (root == null) {
return;
}
invertBinaryTree(root.left);
invertBinaryTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}