878. Boundary of Binary Tree
class Solution {
public:
/**
* @param root: a TreeNode
* @return: a list of integer
*/
vector<int> boundaryOfBinaryTree(TreeNode * root) {
// write your code here
vector<int> res;
if(root == NULL){
return res;
}
vector<int> left;
//findLeftBoundary(root->left, left);
TreeNode *copy = root->left; //这种方法是左右两边边界最后一个会没有取到,最后连起来时,leaves已经包括了,不需要再去重复了。
//这个题开始没有搞出来的原因是,处理left,right时没有从left和right node开始,而是从root开始的,没有分治啊,一定严格分治思想!!!!!!
if(copy != NULL){
while(!(copy->left == NULL && copy->right == NULL)){
left.push_back(copy->val);
if(copy->left != NULL){
copy = copy->left;
}
else{
copy = copy->right;
}
}
}
vector<int> right;
//findRightBoundary(root->right, right); //不应该用root啊,要用root->right, 避免右面是null,但从左边traverse一次,会有重复啊
copy = root->right;
if(copy != NULL){
while(!(copy->left == NULL && copy->right == NULL)){
right.push_back(copy->val);
if(copy->right != NULL){
copy = copy->right;
}
else{
copy = copy->left;
}
}
}
vector<int> leaves;
findLeaves(root, leaves);
//reverse(right.begin(), right.end()); 可以用idex 由大到小操作啊啊啊啊啊
//unordered_set<int> set;
res.push_back(root->val);
for(int i = 0; i < left.size(); i++){
res.push_back(left[i]);
//set.insert(left[i]);
}
for(int i = 0; i < leaves.size(); i++){
res.push_back(leaves[i]);
//set.insert(leaves[i]);
}
for(int i = right.size() - 1; i >= 0; i--){
//if(set.count(right[i]) == 0){
res.push_back(right[i]);
}
return res;
}
void findLeftBoundary(TreeNode *root, vector<int> &left){
if(root == NULL){
return;
}
left.push_back(root->val);
if(root->left != NULL){
findLeftBoundary(root->left, left);
}
else if(root->right != NULL){
findLeftBoundary(root->right, left);
}
}
void findRightBoundary(TreeNode *root, vector<int> &right){
if(root == NULL){
return;
}
right.push_back(root->val);
if(root->right != NULL){
findRightBoundary(root->right, right);
}
else if (root->left != NULL){
findRightBoundary(root->left, right);
}
}
void findLeaves(TreeNode *root, vector<int> &leaves){
if(root == NULL){
return;
}
if(root->left == NULL && root->right == NULL){
leaves.push_back(root->val);
}
findLeaves(root->left, leaves);
findLeaves(root->right, leaves);
}
};
Comments
Post a Comment