LeetCode545.Boundary-of-Binary-Tree
发布时间:2020-12-14 05:18:18 所属栏目:大数据 来源:网络整理
导读:1、头节点为边界节点2、叶结点为边界节点3、如果节点在其所在的层中是最左边或最右边,那么也是边界节点。 思路:分成三部分来做:找左边界结点、叶结点、右边界结点。 找左边界结点要遍历root的左子树,如果左孩子存在就加入vector,否则加入右孩子; 找叶
1、头节点为边界节点 2、叶结点为边界节点 3、如果节点在其所在的层中是最左边或最右边,那么也是边界节点。 思路:分成三部分来做:找左边界结点、叶结点、右边界结点。 找左边界结点要遍历root的左子树,如果左孩子存在就加入vector,否则加入右孩子; 找叶结点,可以利用前序遍历,遍历结点改为判断结点是否是叶结点,是则加入;找右边界结点类似于找左边界结点,不过是其逆序,可以利用一个栈来辅助。 还要注意这三部分会有结点重合,在组合到一起的时候可以利用一个set来去掉重复的结点。注意不能在每个函数中用vector来返回结点中的值,否则无法去除重复的结点,因为树中结点的值不是唯一的,那就指针咯 1 #include <iostream> 2 #include <vector> 3 #include <stack> 4 #include <set> 5 using namespace std; 6 7 struct TreeNode { 8 int val; 9 TreeNode *left; 10 TreeNode *right; 11 TreeNode(int x) : val(x),left(NULL),right(NULL) {} 12 }; 13 14 class Solution { 15 public: 16 void leftMost(TreeNode* root,vector<TreeNode *> &vec) 17 { 18 while(root) 19 { 20 vec.push_back(root); 21 if(root->left) 22 root = root->left; 23 else root = root->right; 24 } 25 } 26 27 void leaf(TreeNode* root,vector<TreeNode *> &vec) 28 { 29 if(root) 30 { 31 if(!root->left && !root->right) vec.push_back(root); 32 if(root->left) 33 leaf(root->left,vec); 34 if(root->right) 35 leaf(root->right,vec); 36 } 37 } 38 39 void rightMost(TreeNode* root,vector<TreeNode *> &vec) 40 { 41 stack<TreeNode *> st; 42 while(root) 43 { 44 st.push(root); 45 if(root->right) 46 root = root->right; 47 else root = root->left; 48 } 49 while(!st.empty()) 50 { 51 vec.push_back(st.top()); 52 st.pop(); 53 } 54 } 55 56 vector<int> boundaryOfBinaryTree(TreeNode* root) { 57 vector<int> ans; 58 if(!root) return ans; 59 vector<TreeNode *> tmp; 60 set<TreeNode *> s; 61 leftMost(root,tmp); 62 leaf(root,tmp); 63 rightMost(root,tmp); 64 for(TreeNode *p : tmp) 65 { 66 if(s.find(p) == s.end()) 67 { 68 ans.push_back(p->val); 69 s.insert(p); 70 } 71 } 72 return ans; 73 } 74 }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |