【题解】二叉树的镜像、判断是不是二叉搜索树

二叉树的镜像

题目链接：二叉树的镜像

解题思路1：递归

对于树的问题，我们可以把整体看作一棵树，把左右子树看作独立的树进行操作，所以对于树的问题，一般情况下都可以考虑用递归来解决

题目代码：

后序版本：

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        //空树返回
        if(pRoot == nullptr) return nullptr;
        //递归子树
        TreeNode* left = Mirror(pRoot->left);
        TreeNode* right = Mirror(pRoot->right);
        TreeNode* temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

先序版本：

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        //空树返回
        if(pRoot == nullptr) return nullptr;
        //递归子树
        TreeNode* temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
        TreeNode* left = Mirror(pRoot->left);
        TreeNode* right = Mirror(pRoot->right);
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法二：深度优先遍历，我们可以借助栈来对二叉树进行遍历

class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot == nullptr) return nullptr;
        stack<TreeNode*> s;
        s.push(pRoot);
        while(!s.empty()){
            TreeNode* node = s.top();
            s.pop();
            if(node->left) s.push(node->left);
            if(node->right) s.push(node->right);
            TreeNode* temp = node->right;
            node->right = node->left;
            node->left = temp;
        }
        return pRoot;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

判断是不是二叉搜索树

题目链接：判断是不是二叉搜索树

解题思路：递归

排除所有非二叉搜索树的情况，反向返回

class Solution {
public:
//中序遍历判断
    long pre = INT_MIN;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        //进入左子树
        if(!isValidBST(root->left)) return false;
        if(root->val <= pre) return false;
        //更新pre值
        pre = root->val;
        //进入右子树
        if(!isValidBST(root->right)) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解题思路2：借助栈来实现遍历，借助数组来保存中序遍历结果，对数组中中序遍历的结果进行比较

二叉搜索树非常特征的一个特征就是二叉搜索树的中序遍历结果是递增的

代码如下：

class Solution {
public:
//利用栈
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;//辅助栈
        vector<int> v;//保存中序遍历结果
        while(root!=nullptr || !s.empty()){
            while(root != nullptr) {
                s.push(root);
                root = root->left;
            }
            TreeNode* node = s.top();
            v.push_back(node->val);
            s.pop();
            //进入右节点
            root = node->right;
        }
        int n = v.size();
        for(int i=0; i<n-1; ++i){
            if(v[i+1] <= v[i]) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24