C#版 - 226. Invert Binary Tree(剑指offer 面试题19) - 题解

时间:2021-07-25 13:58:36

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址

http://blog.csdn.net/lzuacm

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.