897. Increasing Order Search Tree

leetcode easy

#csharp#easy#leetcode#search#tree#two-pointers

Task

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

Пример:

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

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

C# solution

matched/original

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public TreeNode IncreasingBST(TreeNode root) {
        List<TreeNode> nodes = new List<TreeNode>();
        
        Inorder(root, nodes);
        
        for (int i = 0; i < nodes.Count - 1; i++) {
            nodes[i].left = null;
            nodes[i].right = nodes[i + 1];
        }
        
        nodes[nodes.Count - 1].left = null;
        nodes[nodes.Count - 1].right = null;
        return nodes[0];
    }
    
    private void Inorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        Inorder(node.left, nodes);
        nodes.Add(node);
        Inorder(node.right, nodes);
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public TreeNode IncreasingBST(TreeNode root) {
        List<TreeNode> nodes = new List<TreeNode>();
        
        Inorder(root, nodes);
        
        for (int i = 0; i < nodes.size() - 1; i++) {
            nodes[i].left = null;
            nodes[i].right = nodes[i + 1];
        }
        
        nodes[nodes.size() - 1].left = null;
        nodes[nodes.size() - 1].right = null;
        return nodes[0];
    }
    
    private void Inorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        Inorder(node.left, nodes);
        nodes.push_back(node);
        Inorder(node.right, nodes);
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public TreeNode IncreasingBST(TreeNode root) {
        List<TreeNode> nodes = new List<TreeNode>();
        
        Inorder(root, nodes);
        
        for (int i = 0; i < nodes.size() - 1; i++) {
            nodes[i].left = null;
            nodes[i].right = nodes[i + 1];
        }
        
        nodes[nodes.size() - 1].left = null;
        nodes[nodes.size() - 1].right = null;
        return nodes[0];
    }
    
    private void Inorder(TreeNode node, List<TreeNode> nodes) {
        if (node == null) return;
        Inorder(node.left, nodes);
        nodes.add(node);
        Inorder(node.right, nodes);
    }
}

Go solution

matched/original

package main

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

func increasingBST(root *TreeNode) *TreeNode {
    nodes := []*TreeNode{}
    
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        nodes = append(nodes, node)
        inorder(node.Right)
    }
    
    inorder(root)
    
    for i := 0; i < len(nodes)-1; i++ {
        nodes[i].Left = nil
        nodes[i].Right = nodes[i+1]
    }
    
    nodes[len(nodes)-1].Left = nil
    nodes[len(nodes)-1].Right = nil
    return nodes[0]
}

Explanation

Algorithm

Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null.

Вернуть новый корень дерева (первый элемент списка).

😎