『LeetCode』515 在每个树行中找最大值

题目

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

• 二叉树的节点个数的范围是 \([0,10^{4}]\)
• \(-2^{31} <= Node.val <= 2^{31} - 1\)

标签

树, 深度优先搜索, 广度优先搜索, 二叉树

---

题解

【在每个树行中找最大值】常规二叉树遍历の『DFS』&『BFS』

深度优先搜索

记录层数，动态更新每层的最大值即可

# Code language: Python
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        ans = list()

        def dfs(root, h):
            if root:
                if h >= len(ans):
                    ans.append(root.val)
                else:
                    ans[h] = max(ans[h], root.val)
                dfs(root.left, h + 1)
                dfs(root.right, h + 1)

        dfs(root, 0)
        return ans

// Code language: Java
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    public void dfs(TreeNode root, int h, List<Integer> ans) {
        if (root != null) {
            if (h >= ans.size()) ans.add(root.val);
            else ans.set(h, Math.max(ans.get(h), root.val));
            dfs(root.left, h + 1, ans); dfs(root.right, h + 1, ans);
        }
    }
}

// Code language: C++
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ans;
        function<void(TreeNode*, int)> dfs = [&ans, &dfs](TreeNode* root, int h) {
            if (root != nullptr) {
                if (h >= ans.size()) ans.emplace_back(root->val);
                else ans[h] = max(ans[h], root->val);
                dfs(root->left, h + 1); dfs(root->right, h + 1);
            }
        };
        dfs(root, 0);
        return ans;
    }
};

• 时间复杂度: \(O(n)\), \(n\) 表示二叉树结点数量
• 空间复杂度: \(O(n)\)

---

广度优先搜索

分层 BFS，记录每层最大值即可。

# Code language: Python
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        st = deque()
        ans = list()
        if root:
            st.append(root)
        
        while st:
            ans.append(max(node.val for node in st))
            for _ in range(len(st)):
                cur = st.popleft()
                if cur.left: st.append(cur.left)
                if cur.right: st.append(cur.right)
        
        return ans

// Code language: Java
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        if (root != null) st.add(root);

        while (!st.isEmpty()) {
            int val = st.peek().val;
            for (int i = 0, n = st.size(); i < n; ++i) {
                TreeNode cur = st.pollFirst();
                val = Math.max(val, cur.val);
                if (cur.left != null) st.addLast(cur.left);
                if (cur.right != null) st.addLast(cur.right);
            }
            ans.add(val);
        }
        return ans;
    }
}

// Code language: C++
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> st;
        vector<int> ans;
        if (root != nullptr) st.push(root);

        while (!st.empty()) {
            int val = st.front()->val;
            for (int i = 0, n = st.size(); i < n; ++i) {
                TreeNode* cur = st.front();
                st.pop();
                val = max(val, cur->val);
                if (cur->left != nullptr) st.push(cur->left);
                if (cur->right != nullptr) st.push(cur->right);
            }
            ans.push_back(val);
        }
        return ans;
    }
};

• 时间复杂度: \(O(n)\), \(n\) 表示二叉树结点数量
• 空间复杂度: \(O(n)\)

---

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解