114. Flatten Binary Tree to Linked List

LeetCode medium оригинал: C# #backtracking #csharp #leetcode #linked-list #medium #recursion #tree #two-pointers

LeetCode Static

"Связный список" должен использовать тот же класс TreeNode, где указатель на правого ребенка указывает на следующий узел в списке, а указатель на левого ребенка всегда равен null.

"Связный список" должен быть в том же порядке, что и обход бинарного дерева в прямом порядке.

Пример:

Input: root = [1,2,5,3,4,null,6]

Output: [1,null,2,null,3,null,4,null,5,null,6]

C# решение

сопоставлено/оригинал

public class Solution {
    private TreeNode FlattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null) {
            return node;
        }
        TreeNode leftTail = FlattenTree(node.left);
        TreeNode rightTail = FlattenTree(node.right);
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        return rightTail == null ? leftTail : rightTail;
    }
    public void Flatten(TreeNode root) {
        FlattenTree(root);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private TreeNode FlattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null) {
            return node;
        }
        TreeNode leftTail = FlattenTree(node.left);
        TreeNode rightTail = FlattenTree(node.right);
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        return rightTail == null ? leftTail : rightTail;
    }
    public void Flatten(TreeNode root) {
        FlattenTree(root);
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    private TreeNode flattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null) {
            return node;
        }
        TreeNode leftTail = this.flattenTree(node.left);
        TreeNode rightTail = this.flattenTree(node.right);
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        return rightTail == null ? leftTail : rightTail;
    }

    public void flatten(TreeNode root) {
        this.flattenTree(root);
    }
}

JavaScript решение

сопоставлено/оригинал

var flattenTree = function (node) {
    if (node == null) {
        return null;
    }
    if (node.left == null && node.right == null) {
        return node;
    }
    let leftTail = flattenTree(node.left);
    let rightTail = flattenTree(node.right);
    if (leftTail != null) {
        leftTail.right = node.right;
        node.right = node.left;
        node.left = null;
    }
    return rightTail == null ? leftTail : rightTail;
};
var flatten = function (root) {
    flattenTree(root);
};

Python решение

сопоставлено/оригинал

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def flattenTree(self, node: TreeNode) -> TreeNode:
        if not node:
            return None

        if not node.left and not node.right:
            return node

        leftTail = self.flattenTree(node.left)
        rightTail = self.flattenTree(node.right)

        if leftTail:
            leftTail.right = node.right
            node.right = node.left
            node.left = None

        return rightTail if rightTail else leftTail

    def flatten(self, root: TreeNode) -> None:
        self.flattenTree(root)

Go решение

сопоставлено/оригинал

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func flattenTree(node *TreeNode) *TreeNode {
    if node == nil {
        return nil
    }
    if node.Left == nil && node.Right == nil {
        return node
    }
    leftTail := flattenTree(node.Left)
    rightTail := flattenTree(node.Right)
    if leftTail != nil {
        leftTail.Right = node.Right
        node.Right = node.Left
        node.Left = nil
    }
    if rightTail != nil {
        return rightTail
    } else {
        return leftTail
    }
}

func flatten(root *TreeNode) {
    flattenTree(root)
}

Algorithm

1️⃣

Плоское преобразование дерева: Рекурсивно преобразуем левое и правое поддеревья заданного узла, сохраняя соответствующие конечные узлы в leftTail и rightTail.

2️⃣

Установка соединений: Если у текущего узла есть левый ребенок, выполняем следующие соединения:

leftTail.right = node.right

node.right = node.left

node.left = None

3️⃣

Возврат конечного узла: Возвращаем rightTail, если у узла есть правый ребенок, иначе возвращаем leftTail.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.