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]
A:
layer wise traversal
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> largestValues(TreeNode* root) { vector<int> res; vector<TreeNode * > curLayer; if(root) curLayer.push_back(root); while( not curLayer.empty()){ vector<TreeNode * > nextLayer; int maxVal = INT_MIN; for(auto v : curLayer){ maxVal = max(maxVal, v->val ); if(v->left){ nextLayer.push_back(v->left); } if(v->right){ nextLayer.push_back(v->right); } } res.push_back(maxVal); curLayer = nextLayer; // can further use a pointer to avoid copy } return res; } };
错误:
一开始没有检查root 是不是Null
No comments:
Post a Comment