366. Find Leaves of Binary Tree

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    private List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();
    private int GetHeight(TreeNode node) {
        if (node == null) return -1;
        int leftHeight = GetHeight(node.left);
        int rightHeight = GetHeight(node.right);
        int currHeight = Math.Max(leftHeight, rightHeight) + 1;
        pairs.Add(new Tuple<int, int>(currHeight, node.val));
        return currHeight;
    }
    public IList<IList<int>> FindLeaves(TreeNode root) {
        GetHeight(root);
        pairs.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        IList<IList<int>> solution = new List<IList<int>>();
        int currentHeight = -1;
        foreach (var pair in pairs) {
            if (pair.Item1 != currentHeight) {
                solution.Add(new List<int>());
                currentHeight = pair.Item1;
            }
            solution[solution.Count - 1].Add(pair.Item2);
        }
        return solution;
    }
}

#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 x) { val = x; }
}
class Solution {
public:
    private List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();
    private int GetHeight(TreeNode node) {
        if (node == null) return -1;
        int leftHeight = GetHeight(node.left);
        int rightHeight = GetHeight(node.right);
        int currHeight = max(leftHeight, rightHeight) + 1;
        pairs.push_back(new Tuple<int, int>(currHeight, node.val));
        return currHeight;
    }
    public IList<vector<int>> FindLeaves(TreeNode root) {
        GetHeight(root);
        pairs.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        IList<vector<int>> solution = new List<vector<int>>();
        int currentHeight = -1;
        foreach (var pair in pairs) {
            if (pair.Item1 != currentHeight) {
                solution.push_back(new List<int>());
                currentHeight = pair.Item1;
            }
            solution[solution.size() - 1].push_back(pair.Item2);
        }
        return solution;
    }
}

class Solution {
    private List<Pair<Integer, Integer>> pairs;
    
    private int getHeight(TreeNode root) {
        
        if (root == null) return -1;
        
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        int currHeight = Math.max(leftHeight, rightHeight) + 1;

        this.pairs.add(new Pair<Integer, Integer>(currHeight, root.val));

        return currHeight;
    }
    
    public List<List<Integer>> findLeaves(TreeNode root) {
        this.pairs = new ArrayList<>();
        
        getHeight(root);
        
        Collections.sort(this.pairs, Comparator.comparing(p -> p.getKey()));
        
        int n = this.pairs.size(), height = 0, i = 0;

        List<List<Integer>> solution = new ArrayList<>();
        
        while (i < n) {
            List<Integer> nums = new ArrayList<>();
            while (i < n && this.pairs.get(i).getKey() == height) {
                nums.add(this.pairs.get(i).getValue());
                i++;
            }
            solution.add(nums);
            height++;
        }
        return solution;
    }
}

class Solution {
    constructor() {
        this.pairs = [];
    }

    getHeight(node) {
        if (!node) return -1;
        const leftHeight = this.getHeight(node.left);
        const rightHeight = this.getHeight(node.right);
        const currHeight = Math.max(leftHeight, rightHeight) + 1;
        this.pairs.push([currHeight, node.val]);
        return currHeight;
    }

    findLeaves(root) {
        this.getHeight(root);
        this.pairs.sort((a, b) => a[0] - b[0]);
        const solution = [];
        let currentHeight = -1;
        for (const [height, value] of this.pairs) {
            if (height !== currentHeight) {
                solution.push([]);
                currentHeight = height;
            }
            solution[solution.length - 1].push(value);
        }
        return solution;
    }
}

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

class Solution:
    def __init__(self):
        self.pairs = []

    def getHeight(self, node):
        if not node:
            return -1
        leftHeight = self.getHeight(node.left)
        rightHeight = self.getHeight(node.right)
        currHeight = max(leftHeight, rightHeight) + 1
        self.pairs.append((currHeight, node.val))
        return currHeight

    def findLeaves(self, root):
        self.getHeight(root)
        self.pairs.sort()
        solution = []
        currentHeight = -1
        for height, val in self.pairs:
            if height != currentHeight:
                solution.append([])
                currentHeight = height
            solution[-1].append(val)
        return solution

package main

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

type pair struct {
    height, value int
}

type Solution struct {
    pairs []pair
}

func (s *Solution) getHeight(node *TreeNode) int {
    if node == nil {
        return -1
    }
    leftHeight := s.getHeight(node.Left)
    rightHeight := s.getHeight(node.Right)
    currHeight := max(leftHeight, rightHeight) + 1
    s.pairs = append(s.pairs, pair{currHeight, node.Val})
    return currHeight
}

func (s *Solution) findLeaves(root *TreeNode) [][]int {
    s.getHeight(root)
    sort.Slice(s.pairs, func(i, j int) bool {
        return s.pairs[i].height < s.pairs[j].height
    })
    var solution [][]int
    currentHeight := -1
    for _, p := range s.pairs {
        if p.height != currentHeight {
            solution = append(solution, []int{})
            currentHeight = p.height
        }
        solution[len(solution)-1] = append(solution[len(solution)-1], p.value)
    }
    return solution
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

Организовать узлы по высоте и вернуть результат.

😎