[LeetCode] 156. Binary Tree Upside Down 二叉樹(shù)的上下顛倒

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].

這道題讓我們把一棵二叉樹(shù)上下顛倒一下，而且限制了右節(jié)點(diǎn)要么為空要么一定會(huì)有對(duì)應(yīng)的左節(jié)點(diǎn)。上下顛倒后原來(lái)二叉樹(shù)的最左子節(jié)點(diǎn)變成了根節(jié)點(diǎn)，其對(duì)應(yīng)的右節(jié)點(diǎn)變成了其左子節(jié)點(diǎn)，其父節(jié)點(diǎn)變成了其右子節(jié)點(diǎn)，相當(dāng)于順時(shí)針旋轉(zhuǎn)了一下。對(duì)于一般樹(shù)的題都會(huì)有迭代和遞歸兩種解法，這道題也不例外，先來(lái)看看遞歸的解法。對(duì)于一個(gè)根節(jié)點(diǎn)來(lái)說(shuō)，目標(biāo)是將其左子節(jié)點(diǎn)變?yōu)楦?jié)點(diǎn)，右子節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)，首先判斷這個(gè)根節(jié)點(diǎn)是否存在，且其有沒(méi)有左子節(jié)點(diǎn)，如果不滿足這兩個(gè)條件的話，直接返回即可，不需要翻轉(zhuǎn)操作。那么不停的對(duì)左子節(jié)點(diǎn)調(diào)用遞歸函數(shù)，直到到達(dá)最左子節(jié)點(diǎn)開(kāi)始翻轉(zhuǎn)，翻轉(zhuǎn)好最左子節(jié)點(diǎn)后，開(kāi)始回到上一個(gè)左子節(jié)點(diǎn)繼續(xù)翻轉(zhuǎn)即可，直至翻轉(zhuǎn)完整棵樹(shù)，參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if (!root || !root->left) return root;
        TreeNode *l = root->left, *r = root->right;
        TreeNode *res = upsideDownBinaryTree(l);
        l->left = r;
        l->right = root;
        root->left = NULL;
        root->right = NULL;
        return res;
    }
};

下面我們來(lái)看迭代的方法，和遞歸方法相反的時(shí)，這個(gè)是從上往下開(kāi)始翻轉(zhuǎn)，直至翻轉(zhuǎn)到最左子節(jié)點(diǎn)，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        TreeNode *cur = root, *pre = NULL, *next = NULL, *tmp = NULL;
        while (cur) {
            next = cur->left;
            cur->left = tmp;
            tmp = cur->right;
            cur->right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/156

類似題目：

Reverse Linked List

參考資料：

https://leetcode.com/problems/binary-tree-upside-down/

https://leetcode.com/problems/binary-tree-upside-down/discuss/49412/Clean-Java-solution

https://leetcode.com/problems/binary-tree-upside-down/discuss/49432/Easy-O(n)-iteration-solution-Java

https://leetcode.com/problems/binary-tree-upside-down/discuss/49406/Java-recursive-(O(logn)-space)-and-iterative-solutions-(O(1)-space)-with-explanation-and-figure

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(156.二叉樹(shù)的上下顛倒)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)二叉樹(shù)的上下顛倒內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！