题目

Total Accepted: 7094Total Submissions: 13444Difficulty: MediumContributors: µsic_forever

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

Example:

Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9]

Subscribe to see which companies asked this question.

Hide Tags   Tree Depth-first Search Breadth-first Search

https://leetcode.com/problems/find-largest-value-in-each-tree-row/?tab=Description

思路

题目需要找到数的每一层中值最大的点，即深度相同的点中值最大的点。 思路是使用一个数组保存每个深度的最大值，从根出发并遍历节点的时候，记录下走到该点时的深度，与数组中现有的最大值比较，并加上递归的思想。

源程序

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> largestValues(TreeNode* root) { int max[10000],i,maxdep = 0,dep = 0; vector<int> res; for(i = 0;i < 10000;i ++) max[i] = -2147483648; if(root){ dfs(res,root,dep,max,maxdep); for(i = 0;i <= maxdep;i ++) res.push_back(max[i]); } return res; } void dfs(vector<int>& res,TreeNode *root,int dep,int max[],int &maxdep){ if(root->val > max[dep]) max[dep] = root->val; if(dep > maxdep) maxdep = dep; if(root->left != NULL) dfs(res,root->left,dep + 1,max,maxdep); if(root->right != NULL) dfs(res,root->right,dep + 1,max,maxdep); } };