题目描述： 给定一棵二叉树，以逆时针顺序从根开始返回其边界。边界按顺序包括左边界、叶子结点和右边界而不包括重复的结点。 (结点的值可能重复) 左边界的定义是从根到最左侧结点的路径。右边界的定义是从根到最右侧结点的路径。若根没有左子树或右子树，则根自身就是左边界或右边界。注意该定义只对输入的二叉树有效，而对子树无效。 最左侧结点的定义是：在左子树存在时总是优先访问，如果不存在左子树则访问右子树。重复以上操作，首先抵达的结点就是最左侧结点。 最右侧结点的定义方式相同，只是将左替换成右。
示例 1 输入: 输出: [1, 3, 4, 2]
解析: 根不存在左子树，故根自身即为左边界。 叶子结点是3和4。 右边界是1，2，4。注意逆时针顺序输出需要你输出时调整右边界顺序。 以逆时针顺序无重复地排列边界，得到答案[1,3,4,2]。
示例 2 输入:
输出: [1,2,4,7,8,9,10,6,3] 解析: 左边界是结点1,2,4。(根据定义，4是最左侧结点) 叶子结点是结点4,7,8,9,10。 右边界是结点1,3,6,10。(10是最右侧结点) 以逆时针顺序无重复地排列边界，得到答案 [1,2,4,7,8,9,10,6,3]。
方法1： 主要思路： （1）整体思路，想将根节点压入结果中，再将左边界压入结果中，再将叶子结点压入结果中，再将右边界压入结果中； （2）压入根节点，直接压入即可； （3）压入左边界，使用深度遍历，直接遍历到的结点压入到结果中，但不压入叶子结点； （4）压入叶子结点，使用先序遍历，将叶子结点压入到结果中； （5）压入右侧边界，使用深度遍历，直接将遍历到的结点压入到结果中，但不压入叶子结点，但题目要求是逆时针压入，故这里在压入右边界前，先记录当前结果的大小，然后在压入完右侧结点之后，对右侧结点部分进行逆序处理；
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: //压入左侧边界 void add_left_boundy(TreeNode*root,vector<int>&res){ if(root==NULL||root->left==NULL){ return; } root=root->left; while(root->left!=NULL||root->right!=NULL){ res.push_back(root->val); if(root->left!=NULL){ root=root->left; } else{ root=root->right; } } return; } //压入叶子结点 void add_leaf_boundy(TreeNode*root,vector<int>&res){ if(root==NULL){ return; } if(root->left==NULL&&root->right==NULL){ res.push_back(root->val); } add_leaf_boundy(root->left,res); add_leaf_boundy(root->right,res); } //压入右侧结点 void add_right_boundy(TreeNode*root,vector<int>&res){ if(root==NULL||root->right==NULL){ return; } root=root->right; while(root->left!=NULL||root->right!=NULL){ res.push_back(root->val); if(root->right!=NULL){ root=root->right; } else{ root=root->left; } } return; } vector<int> boundaryOfBinaryTree(TreeNode* root) { //处理特殊的情形 if(root==NULL){ return{}; } if(root->left==NULL&&root->right==NULL){ return {root->val}; } //处理根节点 vector<int> res; res.push_back(root->val); //左边界 add_left_boundy(root,res); //叶子结点 add_leaf_boundy(root,res); //保存当前大下，便于后面反序 int cur_size=res.size(); add_right_boundy(root,res);//左边界 //反序处理，保证逆时针要求 reverse(res.begin()+cur_size,res.end()); return res; } };