1、头节点为边界节点
2、叶结点为边界节点
3、如果节点在其所在的层中是最左边或最右边,那么也是边界节点。
思路:分成三部分来做:找左边界结点、叶结点、右边界结点。
找左边界结点要遍历root的左子树,如果左孩子存在就加入vector,否则加入右孩子; 找叶结点,可以利用前序遍历,遍历结点改为判断结点是否是叶结点,是则加入;找右边界结点类似于找左边界结点,不过是其逆序,可以利用一个栈来辅助。 还要注意这三部分会有结点重合,在组合到一起的时候可以利用一个set来去掉重复的结点。注意不能在每个函数中用vector来返回结点中的值,否则无法去除重复的结点,因为树中结点的值不是唯一的,那就指针咯
#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std; struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; class Solution {
public:
void leftMost(TreeNode* root, vector<TreeNode *> &vec)
{
while(root)
{
vec.push_back(root);
if(root->left)
root = root->left;
else root = root->right;
}
} void leaf(TreeNode* root, vector<TreeNode *> &vec)
{
if(root)
{
if(!root->left && !root->right) vec.push_back(root);
if(root->left)
leaf(root->left, vec);
if(root->right)
leaf(root->right, vec);
}
} void rightMost(TreeNode* root, vector<TreeNode *> &vec)
{
stack<TreeNode *> st;
while(root)
{
st.push(root);
if(root->right)
root = root->right;
else root = root->left;
}
while(!st.empty())
{
vec.push_back(st.top());
st.pop();
}
} vector<int> boundaryOfBinaryTree(TreeNode* root) {
vector<int> ans;
if(!root) return ans;
vector<TreeNode *> tmp;
set<TreeNode *> s;
leftMost(root, tmp);
leaf(root, tmp);
rightMost(root, tmp);
for(TreeNode *p : tmp)
{
if(s.find(p) == s.end())
{
ans.push_back(p->val);
s.insert(p);
}
}
return ans;
}
};