【MEDIUM】Binary Tree Upside Down

发布于: 2019-03-03 00:11
阅读: 16
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/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.

For example:

Given a binary tree {1,2,3,4,5},

    1

   / \

  2   3

 / \

4   5

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 || !root->left) {
            return root;
        }
        TreeNode *newRoot = upsideDownBinaryTree(root->left);
        // 左节点->根节点
        // 右节点->左节点
        // 根节点->右节点
        TreeNode *l = root->left;
        TreeNode *r = root->right;
        l->left = r;
        l->right = root;
        root->left = nullptr;
        root->right = nullptr;
        
        return newRoot;
    }
};

循环解法:

class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        TreeNode *cur = root;
        TreeNode *next = nullptr, *pre = nullptr;
        TreeNode *tmp = nullptr;
        
        while (cur) {
            // 左节点->根节点
            next = cur->left;
            // 右节点->左节点
            cur->left = tmp;
            tmp = cur->right;
            // 根节点->右节点
            cur->right = pre;
            
            pre = cur;
            cur = next;
        }
        
        // 最后cur是空,pre是最终根节点
        return pre;
    }
};

Thanks for reading.

All the best wishes for you! 💕