LeetCode #156. Binary Tree Upside Down

题目描述：

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Example:

Input: [1,2,3,4,5] 1 / \ 2 3 / \ 4 5 Output: return the root of the binary tree [4,5,2,#,#,3,1] 4 / \ 5 2 / \ 3 1

Clarification:

Confused what [4,5,2,#,#,3,1] means? Read more below on how binary tree is serialized on OJ.

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

1 / \ 2 3 / 4 \ 5

The above binary tree is serialized as [1,2,3,#,#,4,#,#,5].

class Solution { public: TreeNode* upsideDownBinaryTree(TreeNode* root) { // 右节点要么为空，要么为叶节点，此时左节点一定不为空 if(root==NULL) return NULL; else if(root->left==NULL&&root->right==NULL) return root; // 用迭代的方法需要维护当前节点，上一个节点，上一个节点的右节点，下一个节点 // 每次迭代当前节点的右节点是上一个节点，左节点是上一个节点的右节点 TreeNode* pre=NULL, *cur=root, *next=root->left, *pre_right=NULL; while(cur) { next=cur->left; cur->left=pre_right; pre_right=cur->right; cur->right=pre; pre=cur; cur=next; } return pre; // cur为空时，pre就是最后访问的节点 } }; class Solution { public: TreeNode* upsideDownBinaryTree(TreeNode* root) { // 右节点要么为空，要么为叶节点，此时左节点一定不为空 if(root==NULL) return NULL; else if(root->left==NULL&&root->right==NULL) return root; TreeNode* left=root->left; TreeNode* right=root->right; TreeNode* result=upsideDownBinaryTree(left); left->left=right; left->right=root; root->left=NULL; root->right=NULL; return result; } };