二叉树的遍历

二叉树的遍历：
三种递归遍历:

//前序遍历
void preorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        path.push_back(root->val);
        preorder(root->left, path);
        preorder(root->right, path);
    }
}
//中序遍历
void inorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        inorder(root->left, path);
        path.push_back(root->val);
        inorder(root->right, path);
    }
}
//后续遍历
void postorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        postorder(root->left, path);
        postorder(root->right, path);
        path.push_back(root->val);
    }
}
非递归：
//非递归前序遍历
void preorderTraversal(TreeNode *root, vector<int> &path){
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != NULL || !s.empty())
    {
        while(p != NULL)
        {
            path.push_back(p->val);
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}
//非递归中序遍历
void inorderTraversal(TreeNode *root, vector<int> &path){
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != NULL || !s.empty())
    {
        while(p != NULL)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            path.push_back(p->val);
            s.pop();
            p = p->right;
        }
    }
}


后序非递归遍历：
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> v;
    if(root==nullptr)
        return v;
    stack<TreeNode*> s;
    TreeNode *cur=root;
    TreeNode *pre=nullptr;                  //修改1，增加指向前一结点的指针
    while(cur || !s.empty()){
        while(cur){
            s.push(cur);
            cur=cur->left;
        }
        cur=s.top();
        if(cur->right==nullptr || cur->right==pre){     //修改二，增加判断是否该输出结点
            v.push_back(cur->val);
            s.pop();
            pre=cur;
            cur=nullptr;
        }
        else
            cur=cur->right;
    }
    return v;
}
//层次遍历：如果不需要确定当前遍历到了哪一层，模板如下：
vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> ret;
        if (!root) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            ret.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return ret;
    }
//如果需要知道到了那一层，代码如下：
vector<int> PrintFromTopToBottom(TreeNode* root) {
        int level=0;
        vector<int> ret;
        if (!root) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {

            int sz=q.size();
            while(sz--){
                TreeNode *node = q.front(); 
                q.pop();
                ret.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            level++;
        }
        return ret;
    }

作者：xyTen
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-hou-xu-fei-di-gui-bian-li-liang-chong-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
![图片说明](https://uploadfiles.nowcoder.com/images/20200927/369376673_1601195901210_226A34B686DBDD3B86D0D591CB41B069 "图片标题") 

vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<TreeNode*> s;
        int sum=0;
        vector<vector<int> > v1;
        vector<int> v2;
        if(root==nullptr) return v1;
        TreeNode* cur =root;
        TreeNode* pre =nullptr;
        while(cur!=nullptr || !s.empty()){
            while(cur!=nullptr){
                s.push_back(cur);
                v2.push_back(cur->val);
                sum+=cur->val;
                cur=cur->left;
            }
            cur=s.back();
            if(cur->right==nullptr || cur->right==pre){
                if(cur->left==nullptr && cur->right==nullptr && sum==expectNumber){
                    v1.push_back(v2);
                }
                s.pop_back();
                pre=cur;
                sum-=cur->val;
                v2.pop_back();
                cur=nullptr;
            }
            else{
                cur=cur->right;
            }

        }
        return v1;
    }

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    void mid(TreeNode* p,int a,int &b){
        if(p!=nullptr){
            a+=1;
            if(b==0 && p->right==nullptr && p->left==nullptr){
                b=a;
            }
            else if(b!=0 && p->right==nullptr && p->left==nullptr){
                if(a<b){
                    b=a;
                }
            }
            mid(p->left,a,b);            
            mid(p->right,a,b);
        }
    }

    int minDepth(TreeNode* root) {
        int a=0;
        int b=0;
        mid(root,a,b);
        return b;
    }
};