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

Popular posts from this blog

1427. Split Array into Fibonacci Sequence

Amazon OA 763. Partition Labels

05/25 周一