Leetcode 114. Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List :

給定一個二元樹( binary tree)，把它轉換成一個只有右子樹的linked list

Python

DFS :右指針指向列表中的下一個節點，左指針始終為空

class Solution(object):
    def flatten(self, root):

        nodes = []
        def dfs(root):
            if root:
                nodes.append(root)
                dfs(root.left)
                dfs(root.right)
        dfs(root)
        N = len(nodes)
        for i in range(1, N):
            pre, cur = nodes[i-1], nodes[i]
            pre.left = None
            pre.right = cur

節點的左子樹為空，則不需要進行操作，如果某節點的左子樹不為空，則左子樹中在最後一個節點是左子樹中的右節點，我們只需要將該節點的右子樹轉移到左子樹的右節點即可。

class Solution(object):
    def flatten(self, root):

        while root:
            if root.left:
                pre  = next = root.left
                while pre.right:
                    pre = pre.right
                pre.right = root.right
                root.left = None
                root.right = next
            root = root.right

C++

首先我們可以觀察到展開後的鍊錶的先序遍歷是二叉樹的先序遍歷。展開為鍊錶後，原來的左子樹會成為鍊錶的右子樹，而原來的右子樹會接在新的右子樹的末端。所以我們可以對於每一個節點，先將其左子樹接到右子樹上，然後將原來的右子樹接到新的右子樹的末端。具體實現上，我們可以使用遞歸來實現。對於當前節點，我們先遞歸地將其左子樹和右子樹展開為鍊錶，然後將左子樹接到右子樹的位置，將原來的右子樹接到新的右子樹的末端。需要注意的是，我們需要用一個臨時變量保存原來的右子樹，以防止在遞歸過程中丟失右子樹。

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->left);
        flatten(root->right);
        TreeNode* tmp = root->right;
        root->right = root->left;
        root->left = nullptr;
        while (root->right) root = root->right;
        root->right = tmp;
    }
};

Python

C++

相關