刷树专题有感

1.验证二叉搜索树
这个题，一开始我以为，只要保证每一个分支都是左孩子<节点<右孩子就可了。
忘了二叉搜索树是保证左子树都比根节点小，右子树都比根节点大，且左右子树又分别是二叉搜索树。
注意观察，会发现，二叉搜索树的主要特点，对于每一个节点，都必须满足：
如果是左树节点则小于根节点，如果是右树节点则大于根节点。
因此，只需要维护最小值和最大值即可。如是左树，则当前节点为最大值，如是右树，则当前节点是最小值
代码实现如下:

bool helper(TreeNode *root,long long lower,long long upper){
    /*recursion*/
    //base case
    if(!root)    return 1;
    if(root->val<=lower||root->val>=upper)    return 0;
    //operations
    return helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);
}
bool isValidBST(TreeNode* root){
    return helper(root,LONG_MIN,LONG_MAX);
}

总结下：因此，可以认为二叉搜索树的特点其实就是，维护住最小值和最大值，并不断的更新最大值和最小值，保障每一个节点都是满足的介于最大值最小值之间。用代码描述就是下面两句：

/*二叉搜索树的核心特征：*/
if(root->val<=lower||root->val>=upper)    return 0;
helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);

2.判断一颗二叉树是否是搜索二叉树和完全二叉树
因为判断二叉树是否是搜索二叉树已经在第一个题目中做了。因此这里就只针对如何判断二叉树是否是完全二叉树。
大概想了想，如果递归的话，只能判断是否是满二叉树，即每一次都判断节点的左右节点是否同时存在或同时不存在，如果是就返回1，否则就不是满二叉树。
要判断是否是完全二叉树，还得判断在最后一层前是满二叉树，但最后一层就未必满了，只要保证节点靠左就可以了，因此递归的话，就没办法做到。
为此，需要用层序遍历来实现，但是又有一个问题，层序遍历怎么记录层数呢，其实记录层数也好办。只需要每次操作层序遍历前获取队列长度，即是该层节点数，然后再遍历。
但是，记录层数，维护这种关系太麻烦了，有个比较简便的做法。算一种技巧。
我们只需要改一下层序遍历的结构就行了。首先，我们不断把非空节点的左右节点都放入队列，当我们遇到了空节点时，这是队列内就一定全是空节点，否则就不是完全二叉树。

/*按层输出的层序遍历*/
void levelSearch(TreeNode* root){
    queue<TreeNode*>q;q.push(root);
    while(!q.empty()){
        int size=q.size();//记录该层所含节点数
        for(int i=0;i<size;++i){//遍历该层节点
            TreeNode *cur=q.front();
            printf("%d",cur->val);//遍历的操作
            if(cur->left)    q,push(cur->left);
            if(cur->right)    q.push(cur->right);
            q.pop();  
        }
    }
}
/*判断是否是完全二叉树*/
bool isCBT(TreeNode* root){
    queue<TreeNode *>q;q.push(root);
    TreeNode *front=nullptr;
    while(front=q.front()){
        q.push(front->left);
        q.push(root->right);
        q.pop();
    }
    while(!q.empty()){
        if(q.front()!=nullptr)    return 0;
        q.pop();
    }
    return 1;
}

3.二叉树的深度
这个题有两种做法，其实对于树或图的遍历无非两种，DFS或BFS，DFS包括前序、中序、后序遍历，BFS则是层序遍历。DFS涉及到递归，往往代码量较少，但费解耗时，而BFS涉及到对节点队列的灵活使用，也不容易。

/*深度优先遍历：后序遍历*/
int maxDepth(TreeNode *root){
    //base case
    if(!root)    return 0;
    //operations
    return max(maxDepth(root->left),maxDepth(root->right))+1;
}

DFS其实可以直接去想就行了，无需过分纠结递归过程，找到base case 和operations 就行。
因此，BFS就显得更难了点。下面大概总结下目前已知的BFS对队列的几种使用方式：
(1)在队列中控制我们想要取出的节点：通过更新队列或者通过控制输出次数来达到目的---两种方法是一样的。
控制输出次数见第2题按层输出的层序遍历。
更新队列，见这题代码：只要每一次让队列变为直含当前层的节点，那么就可以计算层数，从而得到深度。

int maxDepth(TreeNode* root){
    queue<TreeNode *>q;q.push(root);
    int res=0;
    while(!q.empty()){
        //创建一个新的队列，存该层节点
        queue<TreeNode *>tmp;
        while(!q.empty()){
            TreeNode *cur=q.front();q.pop();
            if(cur->left)    tmp.push(cur->left);
            if(cur->right)    tmp.push(cur->right);
        }
        q=tmp;//更新队列，控制节点队列始终只含该层的节点
        ++res;
    }
    return res;
}

(2)改变进队列原则---具体怎么变看技巧，要慢慢总结
比如第2题，判断是否是完全二叉树，我们进队列的原则是，该节点不为空，那么就放入它的左右节点。具体见上面第2题代码。

刷 树专题 有感

全站热榜

刷树专题有感