LintCode 175. Invert Binary Tree 原创Java参考解答

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

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注