题目

给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空，将此二叉树上下翻转并将它变成一棵树， 原来的右节点将转换成左叶节点。返回新的根。

解题思路

【leetcode题解】C 颠倒二叉树超详细图解 - 图1

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     TreeNode* upsideDownBinaryTree(TreeNode* root) {
  13.         TreeNode * tmp;
  14.         TreeNode * resultfromLeft;
  15.         if(root == NULL || root->left == NULL) return root;
  16.         resultfromLeft = upsideDownBinaryTree(root->left);
  17.         tmp = resultfromLeft;
  18.         while(tmp->right != NULL) tmp = tmp->right;
  19.         tmp->right = root;
  20.         tmp->left = root->right;
  21.         root->left = root->right = NULL;
  22.         return resultfromLeft;
  23.     }
  24. };