AM MS 878. Boundary of Binary Tree
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: a TreeNode
* @return: a list of integer
*/
void findLeaves(TreeNode *root, vector<int> &res){
if(root == NULL){
return;
}
if(root->left == NULL && root->right == NULL){
res.push_back(root->val);
}
findLeaves(root->left, res);
findLeaves(root->right, res);
return;
}
vector<int> boundaryOfBinaryTree(TreeNode * root) {
// write your code here
//这种题就要拼思路了,有思路很简单。没思路现象,容易走错路。
//1, 找leaves。
//2, 找左边界。
//3, 找右边界。
vector<int> res;
if(root == NULL){
return res;
}
vector<int> lefts;
lefts.push_back(root->val);
TreeNode *left = root->left;
if(left != NULL){
while(!(left->left == NULL && left->right == NULL)){
lefts.push_back(left->val);
if(left->left){
left = left->left;
}
else if(left->right){
left = left->right;
}
}
}
vector<int> rights;
rights.push_back(root->val);
TreeNode *right = root->right;
if(right != NULL){
while(!(right->left == NULL && right->right == NULL)){
rights.push_back(right->val);
if(right->right){
right = right->right;
}
else if(right->left){
right = right->left;
}
}
}
vector<int> leaves;
findLeaves(root, leaves);
lefts.insert(lefts.end(), leaves.begin(), leaves.end());
lefts.insert(lefts.end(), rights.rbegin(), rights.rend());
lefts.pop_back();
return lefts;
}
};
Comments
Post a Comment