好的，所以我正在研究我的演算法和資料結構知識，并且我正在嘗試在二叉樹的每個級別中找到最大的數字。我不確定我的邏輯有什么問題。
class Solution
{
int maxLevel = 0;
public ArrayList<Integer> largestValues(Node root)
{
//code here
ArrayList<Integer> arr = new ArrayList<>();
checkHeight(root, 1, arr);
return arr;
}
void checkHeight(Node root, int height, ArrayList<Integer> arr){
if(root == null){
return;
}
if(maxLevel < height){
if(root.left != null && root.right != null){
arr.add(Math.max(root.left.data, root.right.data));
}
if(root.left != null && root.right == null){
arr.add(root.left.data);
}
if(root.left == null && root.right != null){
arr.add(root.right.data);
}
if(root.left == null && root.right == null){
return;
}
maxLevel = height;
}
checkHeight(root.left, height 1, arr);
checkHeight(root.right, height 1, arr);
}
}
uj5u.com熱心網友回復：
您似乎不熟悉二叉樹的每一層中的最大數的含義。您當前的實作采用節點的左右子節點中最大的一個，如果它只有一個子節點，則該子節點。
二叉樹中的一個級別由具有相同深度的所有節點組成，無論它們是否是同一父級的直接子級。
因此，您的演算法從根本上是錯誤的。
有兩種方法可以解決這個問題：DFS 和 BFS。
BFS 更直接，或者至少在我看來。事情是這樣的：
- 逐級回圈節點（BFS 設計的那樣）。
- 取最大元素。
- 移動到下一個級別。
DFS 的作業原理如下：
- 保留一個字典，將級別作為鍵映射到級別中的最大數字作為值。
- 當你潛入 dfs 時，使用遞回函式的引數來跟蹤深度。
- 在每個節點上，如果當前節點更大，則更新該級別的鍵值。
- 最后將您的字典轉換為您需要的任何格式。注意：您使用哪種 DFS 風格（有序、預購等）并不重要。只要確保訪問每個節點并跟蹤深度即可。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/410212.html
標籤：