問題：

You need to find the largest value in each row of a binary tree.
Example:

Input:

image.png

Output: [1, 3, 9]

大意：

你需要找到二叉樹中每一行最大的值。
例子：

輸入：

image.png

輸出： [1, 3, 9]

思路：

要找每一行最大的數(shù)，我們總歸是要遍歷二叉樹的，遍歷二叉樹分為BFS和DFS，這里我們要找每行最大的數(shù)，那么我們就用BFS，一行行分析過去。

還記得我們在傳送門：LeetCode筆記：102. Binary Tree Level Order Traversal中，是要求將二叉樹一層層地輸出出來。那么通過同樣的方法，我們用利用隊列的先進先出特性，依次保留每一行新讀進來的節(jié)點。用一個變量記錄當前行的總節(jié)點數(shù)，然后對每一行都去尋找最大的節(jié)點值是多少，記錄在結果中就可以了。

代碼（Java）：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        List<Integer> res = new LinkedList<Integer>();
        if (root == null) return res;
        
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelNum = queue.size();
            int temp = queue.peek().val;
            if (queue.peek().left != null) queue.offer(queue.peek().left);
            if (queue.peek().right != null) queue.offer(queue.peek().right);
            queue.poll();
            for (int i = 1; i < levelNum; i++) {
                if (queue.peek().val > temp) temp = queue.peek().val;
                if (queue.peek().left != null) queue.offer(queue.peek().left);
                if (queue.peek().right != null) queue.offer(queue.peek().right);
                queue.poll();
            }
            res.add(temp);
        }
        return res;
    }
}

他山之石：

除了用BFS，其實DFS也可以做，但是就需要有一個參數(shù)來記錄當前節(jié)點所在的行，同時對于每次遇到的新節(jié)點，判斷該節(jié)點值與已經(jīng)記錄的所在行的最大值之間的大小，如果更大就替換掉結果中記錄的值，如果小一些那就略過。這個方法運行起來會比我的方法要快。

public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        helper(root, res, 0);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res, int d){
        if(root == null){
            return;
        }
       //expand list size
        if(d == res.size()){
            res.add(root.val);
        }
        else{
        //or set value
            res.set(d, Math.max(res.get(d), root.val));
        }
        helper(root.left, res, d+1);
        helper(root.right, res, d+1);
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首頁