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