树

二叉树的前序遍历

class Solution {
    vector<int> a;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        d(root);
        return a;
    }

    void d(TreeNode* x)
    {
        if(x==NULL)
        return;
        a.push_back(x->val);
        d(x->left);
        d(x->right);
    }
};

二叉树的中序遍历

class Solution {
    vector<int> a;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        d(root);
        return a;
    }

    void d(TreeNode* x)
    {
        if(x==NULL)
        return;
        d(x->left);
        a.push_back(x->val);
        d(x->right);
    }
};

二叉树的后序遍历

class Solution {
    vector<int> a;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        d(root);
        return a;
    }

    void d(TreeNode* x)
    {
        if(x==NULL)
        return;
        d(x->left);
        d(x->right);
        a.push_back(x->val);
    }
};

二叉树的最大深度

class Solution {
    int a;
public:
    int maxDepth(TreeNode* root) {
        a=0;
        d(root,0);
return a;
    }
    void d(TreeNode* x,int y)
    {
        if(x==NULL)
        {
            if(y>a)
            a=y;
        }
        else
        {
            d(x->left,y+1);
d(x->right,y+1);
        }

    }
};

二叉树的层次遍历（队列 + BFS）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while (!q.empty()) {
            vector<int> a;
            for (int i = q.size() - 1; i >= 0; --i) {
                TreeNode* tmp = q.front(); q.pop();
                a.emplace_back(tmp->val);
                if (tmp->left) q.push(tmp->left);
                if (tmp->right) q.push(tmp->right);
            }
            ans.emplace_back(a);
        }
        return ans;
    }
};

判断一个树是否是一个有效的二叉搜索树的方法：中序遍历，如果是二查搜索书应该是升序的。

二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。