C#版 - 226. Invert Binary Tree - 题解

在线提交: https://leetcode.com/problems/invert-binary-tree/ 或 http://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171

题目描述

Invert a binary tree.

Example:

Input:

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

Output:

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

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

• Difficulty: Easy
• Total Accepted: 238.9K
• Total Submissions: 443.1K Related Topics Tree

思路: 交换左右子树的根节点，再递归地交换两棵子树的叶节点即可。当原树为null时，直接返回null~

已AC代码:

// Definition for a binary tree node.
//public class TreeNode
//{
//    public int val;
//    public TreeNode left;
//    public TreeNode right;
//    public TreeNode(int x) { val = x; }
//}
public class Solution
{
    public TreeNode InvertTree(TreeNode root)
    {
        if(root == null)
            return null;

        TreeNode p;
        p = root.left;                
        root.left = root.right;
        root.right = p;

        InvertTree(root.left);
        InvertTree(root.right);
        return root;
    }
}

Rank: You are here! Your runtime beats 95.68 % of csharp submissions.