题目来源

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

题目描述

题目解析

层次遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {
public List<Integer> largestValues(TreeNode root) {List<Integer> list = new LinkedList<>();if (root == null){return list;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){int size = queue.size();int max = Integer.MIN_VALUE;for (int i = 0; i < size; i++){TreeNode pop = queue.poll();if (pop.val > max){max = pop.val;}if (pop.left != null){queue.offer(pop.left);}if (pop.right != null){queue.offer(pop.right);}}list.add(max);}return list;}
}

vector<int> largestValues(TreeNode* root) {vector<int> vec;if(root == NULL){return vec;}std::queue<TreeNode* > queue;queue.push(root);while (!queue.empty()){int size = queue.size();int max = INT_MIN;for (int i = 0; i < size; ++i) {TreeNode *node = queue.front();queue.pop();if(node->val > max){max = node->val;}if(node->left){queue.push(node->left);}if(node->right){queue.push(node->right);}}vec.push_back(max);}return vec;
}

深度遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {
public List<Integer> largestValues(TreeNode root) {List<Integer> list = new LinkedList<>();helper(root, 0, list);return list;}private void helper(TreeNode root, int level, List<Integer> list){if (root == null){return;}if (list.size() == level){list.add(level, root.val);}int max = Math.max(root.val, list.get(level));list.set(level, max);helper(root.left, level + 1, list);helper(root.right, level + 1, list);}
}