翻转二叉树(LeetCode226. 翻转二叉树)

11月11日面试题

题目

解析

据说Homebrew的作者Max Howell在面试Google时，无法在白板上写出这道题，而遭到了淘汰。因此关于面试时算法题这种考察形式，业内一直存在争论。

递归实现。从根节点起先翻转它的左右子树，然后以左右子树为根节点分别递归翻转。

代码

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    //递归翻转左右子树
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    //右子树和左子树交换位置
    root.left = right;
    root.right = left;

    return root;
}