Leetcode 114. Flatten Binary Tree to Linked List

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