LeetCode 545. 二叉树的边界（前序+后序）*

示例 1
输入:
  1
   \
    2
   / \
  3   4
输出:
[1, 3, 4, 2]
解析:
根不存在左子树，故根自身即为左边界。
叶子结点是3和4。
右边界是1，2，4。注意逆时针顺序输出需要你输出时调整右边界顺序。
以逆时针顺序无重复地排列边界，得到答案[1,3,4,2]。

示例 2
输入:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
       
输出:
[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]。

class Solution {
	vector<int> ans;
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
    	if(!root) return {};
    	ans.push_back(root->val);
    	dfs(root->left, -1);
    	dfs(root->right, 1);
    	return ans;
    }
    void dfs(TreeNode* root, int dir)
    {
    	if(!root) return;
    	if(dir == -1)//左边界
    	{
    		ans.push_back(root->val);//前序遍历
    		if(root->left)
    		{	
    			dfs(root->left,-1);//有左节点，进入左节点找
    			dfs(root->right, 0);//舍弃右节点
    		}
    		else
    			dfs(root->right,-1);//没有左节点，当成左边界
    	}
    	else if(dir == 1)//右边界
    	{
    		// ans.push_back(root->val);//写这里错了
    		if(root->right)
    		{
    			dfs(root->left,0);
    			dfs(root->right, 1);
    		}
    		else
    			dfs(root->left, 1);
    		ans.push_back(root->val);//应该是后序遍历
    	}
    	else//dir==0，非左右边界，找叶子节点
    	{
    		if(!root->left && !root->right)
    			ans.push_back(root->val);
    		dfs(root->left, 0);
    		dfs(root->right, 0);
    	}
    }
};