二叉树常见题型(1)

目录

1.翻转二叉树

2.对称二叉树

3.二叉树的最大深度

4.二叉树的最小深度

5.相同的树

6.二叉树的右视图

7.?完全二叉树的节点个数

8.平衡二叉树

9.验证二叉搜索树

---

? ? ? ?做二叉树的题目最常见的做法就是递推和迭代，而一般我们更青睐递推，在我们写递推的时候，我们不能陷入到细节中，我们只需要关注边界条件和单层逻辑，你想一步一步的把递推的细节过程想明白？这难道不是很麻烦吗？只要边界条件和单层逻辑没有问题，结果也是没问题的，这也是数学归纳法的逻辑。

1.翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)return root;
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

? ? ? ?就像这道题，我们的子问题就是把每个节点的左子树和右子树都交换，结束递归的边界条件就是当root为空时，我们就可以进行回溯了，这是边界条件；接下来确定单层逻辑，每次交换该节点的左子树和右子树，之后来到该节点的左子树和右子树执行该操作，这就是单层逻辑，最后返回根节点即可。

2.对称二叉树

class Solution {
public:
    bool check(TreeNode* p,TreeNode* q)
    {
       if(p==NULL&&q==NULL)return true;
       if(p&&q&&p->val==q->val)
          return check(p->left,q->right)&&check(p->right,q->left);
       else return false;
       
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left,root->right);
    }
};

? ? ? 这道题的子问题就是让我们比较每个节点左子树的左子树和右子树的右子树，每个节点左子树的右子树和右子树的左子树是否相等。边界条件是p和q同时为空返回true，或者p和q不为空且值相等，这时候我们继续p的左子树和q的右子树，p的右子树和q的左子树是否相等，其他情况返回false即可。

3.二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        return 1+max(maxDepth(root->left), maxDepth(root->right));
    }
};

? ? ? 这个也是需要遍历，遍历的时候我们用递推，边界条件就是遍历的节点为空时返回0，其他情况下我们返回左右子树的最大深度的较大值，别忘了加1，因为最初的根节点也要算。

4.二叉树的最小深度

? ? ? 这个题我们可能会想，这不是水题吗？上一题的代码把max改成min不就行了，我刚开始也是这样想的，其实不然

? ? ?最小深度是从根节点到最近叶子节点的最短路径上的节点数量，左右子树都为空的节点才是叶子节点，如果这样求的话，没有左子树的节点会被认为是最小深度，正确的做法如下：?

? ? ?如果左子树为空，右子树不为空，最小深度就是1+右子树的深度；如果右子树为空，左子树不为空，最小深度就是1+左子树的深度，最后如果左右子树都不为空，返回左右子树最小深度的较小值+1。

?
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right != NULL) {
            return 1 + minDepth(root->right);
        }
        if (root->left != NULL && root->right == NULL) {
            return 1 + minDepth(root->left);
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

?

5.相同的树

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
         if(p==NULL&&q==NULL)return true;
         if(p&&q&&p->val==q->val)
         return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
         else return false;
    }
};

? ? ?这道题和对称二叉树很像 ，其实是一样的，边界条件是p和q为空时返回true，p和q不为空且值相等时，返回p的左子树和q的左子树，p的右子树和q的右子树的比较结果的与的运算结果，其他情况返回false。

6.二叉树的右视图

class Solution {
public: 
    vector<int>vec;
    vector<int> right(TreeNode* cur,int depth)
    {
       
        if(cur==NULL)return vec;
        if(depth==vec.size())vec.push_back(cur->val);
        right(cur->right,depth+1);
        right(cur->left,depth+1);
        return vec;
    }
    vector<int> rightSideView(TreeNode* root) {
         right(root,0);
         return vec;
    }
};

? ? ? 这道题既然要找右视图，那我们可以先递归右子树，再递归左子树，那我们怎么记录答案，以及如何判断节点是需要记录的答案，我们需要在递归的同时记录递归深度，如果递归深度等于答案的长度，我们就需要记录到答案中。

7.?完全二叉树的节点个数

class Solution {
public:
    int getNodeNum(TreeNode* cur)
    {
        if(cur==NULL)return 0;
        int leftNum=getNodeNum(cur->left);
        int rightNum=getNodeNum(cur->right);
        int treeNum=leftNum+rightNum+1;
        return treeNum;
    }
    int countNodes(TreeNode* root) {
         return getNodeNum(root);
    }
};

? ? ? 这个题的子问题就是分别求节点的左子树和右子树的节点个数，不断递推。首先确定边界条件，就是节点为空时返回0，分别求左子树和右子树的节点个数，最后返回的时候要+1，因为根节点也是节点。

8.平衡二叉树

class Solution {
public:
    int getHeight(TreeNode* cur)
    {
       if(cur==NULL)return 0;
       int left=getHeight(cur->left);
       if(left==-1)return -1;
       int right=getHeight(cur->right);
       if(right==-1)return -1;
       return  abs(left-right)>1?-1:1+max(left,right);
    }
    bool isBalanced(TreeNode* root) {
         return getHeight(root)==-1?false:true;
    }
};

? ? ?我们需要求左子树和右子树的高度，但如果我们在递推的过程中已经不是平衡二叉树了，我们就可以结束递推，又因为高度都为非负数，所以如果不是平衡二叉树我们就可以返回-1，如果是我们就返回1+左右子树高度的较大值。

9.验证二叉搜索树

?

? ? ?二叉搜索树每个节点的左子树的值小于节点值，右子树的值大于节点值，上面的二叉搜索树有这样的特点，我们可以用一个区间来判断是否为二叉搜索树，对于根节点来说，我们传入负无穷到正无穷的区间，对于根节点的左子树，判断它是否在负无穷到5的区间内，以此类推，每次更新区间，不断递推，得到答案

class Solution {
public:
    bool check(TreeNode* cur,long left,long right)
    {
        if(cur==NULL)return true;
        long x=cur->val;
        return left<x&&x<right&&check(cur->left,left,x)&&check(cur->right,x,right);
    }
    bool isValidBST(TreeNode* root) {
        return check(root,LONG_MIN,LONG_MAX);
    }
};