leetcode 二叉树展开为链表 中等

leetcode 二叉树展开为链表 中等

 

 

 

此题的关键部分就是如何处理 右儿子如何连接在左儿子上,然后再由左儿子变成父亲的右儿子。

现假设为一种最简单的情况:

  O (a)

   /       \

O (b)    O (c)

显然,节点 c 需要的得到的点是节点 b

    O (a)

     /       \

  O (b)    O (c)

   \

    O (d)

节点 c 需要的点是节点 d.

所以,对于当前父亲节点,其左儿子中最右下的那个值,就是其右儿子的前驱。如果左儿子没有往右的值,最左下的值就是右儿子的前驱。

还是代码解释的清楚:

class Solution {
public:
    void flatten(TreeNode* root) {
        auto _ = solve(root);
    }

    TreeNode *solve(TreeNode *root) {
        if(root == nullptr) return root;
        auto retLef = solve(root -> left);
        auto retRig = solve(root -> right);
        if(retLef) {
            retLef -> right = root -> right;
            root -> right = root -> left;
            root -> left = nullptr;
        }
        return retRig ? retRig : (retLef ? retLef : root);      // 返回的值为兄弟节点的前驱
    }
};

 

再贴一个官方的:

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *curr = root;
        while (curr != nullptr) {
            if (curr->left != nullptr) {
                auto next = curr->left;
                auto predecessor = next;
                while (predecessor->right != nullptr) {
                    predecessor = predecessor->right;
                }
                predecessor->right = curr->right;
                curr->left = nullptr;
                curr->right = next;
            }
            curr = curr->right;
        }
    }
};

leetcode 二叉树展开为链表 中等

上一篇:Vue很难?看完这篇文章,让你快速上手Vue


下一篇:TCP/IP协议