# 22、二叉树层序遍历

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> ret;
queue<TreeNode*> q;

if(root==nullptr)return ret;
q.push(root);
while(!q.empty())
{
TreeNode*node=q.front();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
ret.push_back(node->val);
q.pop();
}
return ret;
}
};

# 23、二叉树的后序遍历序列

class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.empty())return false;

int end=sequence.size()-1;
int root=sequence[end];//root是根节点的val

int i=0;
bool flag=false;
for(;i<end;i++)
{
if(sequence[i]>root)//说明i已经指向右树节点了
flag=true;
else //应该是左树节点
{
if(flag)
return false;
}
}
return true;
}
};

# 24、二叉树中和为某一值得路径

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
vector<vector<int>> ret;
vector<int> path;
if (root)
DFS(root, expectNumber, ret, path);
return ret;
}
void DFS(TreeNode*root, int sum, vector<vector<int>>&ret, vector<int>& path)
{
path.push_back(root->val);
if (!root->left&&!root->right)
{
if (root->val == sum)
ret.push_back(path);
}
if (root->left)
DFS(root->left, sum-root->val, ret, path);
if (root->right)
DFS(root->right, sum-root->val, ret, path);
path.pop_back();
}
};