366. Find Leaves of Binary Tree
leetcode medium
#csharp#leetcode#math#medium#recursion#search#sort#tree#two-pointers
Task
Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.
Пример:
Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.
C# solution
matched/originalusing 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;
}
}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 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;
}
}Java solution
matched/originalclass 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;
}
}JavaScript solution
matched/originalclass 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;
}
}Python solution
matched/originalclass 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 solutionGo solution
matched/originalpackage 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
}Explanation
Algorithm
Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.
Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.
Организовать узлы по высоте и вернуть результат.
😎