C++怎么實現(xiàn)二叉樹的上下顛倒

這篇文章主要講解了“C++怎么實現(xiàn)二叉樹的上下顛倒”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++怎么實現(xiàn)二叉樹的上下顛倒”吧！

二叉樹的上下顛倒

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

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

解法二：

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;
    }
};

感謝各位的閱讀，以上就是“C++怎么實現(xiàn)二叉樹的上下顛倒”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對C++怎么實現(xiàn)二叉樹的上下顛倒這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！