二叉树每一层的最大值

Question

好的，所以我正在研究我的算法和数据结构知识，并且我正在尝试在二叉树的每个级别中找到最大的数字。我不确定我这里的逻辑有什么问题。

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);
    }
    
}

Answer 1

看来您不熟悉二叉树每一层的最大数是什么意思。您当前的实现采用节点的左右子节点中最大的一个，如果它只有一个子节点，则该子节点。

二叉树中的一个级别由具有相同深度的所有节点组成，无论它们是否是同一父节点的直接子节点。

因此你的算法从根本上是错误的。

有两种方法可以解决这个问题：DFS 和 BFS。

BFS 更直接，至少在我看来是这样。这是怎么回事：

逐层遍历节点（BFS 设计这样做）。
取最大元素
进入下一个级别。

DFS 的工作原理如下：

保留一个字典，将级别作为键映射到级别中的最大数字作为值。
当你潜水 dfs 时，使用递归函数的参数跟踪深度。
在每个节点，如果当前节点更大，则更新该级别的键值。
最后将您的字典转换为您需要的任何格式。注意：使用哪种类型的 DFS（有序、预序等）并不重要。只要确保访问每个节点并跟踪深度即可。

二叉树每一层的最大值

Largest value in each level of a binary tree

java

algorithm

data-structures

recursive-datastructures