Day23 617合并二叉树 700二叉搜索树中的搜索 98验证二叉搜索树

617合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为?NULL 的节点将直接作为新二叉树的节点。

class Solution {
public:
    //迭代法
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr) return root2; //如果树1为空就返回树2，下面同理
        if(root2==nullptr) return root1;
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2); //让两个根节点入队
        //直到没有能继续往下处理的元素的时候，就停止循环
        while(!que.empty()){
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();

            //此时两个节点都不为空，直接相加值返回给root1；
            node1->val += node2->val;

            //两个node的左节点都不为空，加入队列里后面相加
            if(node1->left && node2->left){
                que.push(node1->left);
                que.push(node2->left);
            }

            //两个node的右节点都不为空，加入队列里后面相加
            if(node1->right && node2->right){
                que.push(node1->right);
                que.push(node2->right);
            }

            //node1的左节点为空，node2的左节点不为空，直接赋值（赋的是node2下面的一整串树哦）
            if(!node1->left && node2->left) node1->left = node2->left;

            //node1的右节点为空，node2的右节点不为空，直接赋值（赋的是node2下面的一整串树哦）
            if(!node1->right && node2->right) node1->right = node2->right;
            
            //node1不为空，node2为空的情况不需要处理，因为最后都是整合带node1上
        }
        return root1;
    }
};

class Solution {
public:
    //递归法
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1) return root2; //如果root1为空就返回root2
        if(!root2) return root1; //如果root2为空就返回root1
        
        //采用前序的方法，当然中序后序只是代码简单换了一下位置
        root1->val += root2->val;//如果都不为空就把两棵树的数值都加入到root1上面

        root1->left = mergeTrees(root1->left, root2->left); //root1的左子树建立
        root1->right = mergeTrees(root1->right,root2->right); //root2的左子树建立

        return root1; //返回的结果就是root1
    }
};

700 二叉搜索树中的搜索

?给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

?

class Solution {
public:
    //迭代法
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root){
            if(root->val > val) root = root->left;
            else if(root->val < val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};

class Solution {
public:
    //递归法：
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root || root->val == val) return root; //如果为空返回null，等于val返回root
        TreeNode* result; //接收结果
        //二叉搜索树BST的定义就是右面全是大，左面全是小
        if(val > root->val) result = searchBST(root->right, val);
        if(val < root->val) result = searchBST(root->left, val);
        return result;
    }
};

98 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

class Solution {
    //利用转化数组的递归法
public:
    vector<int> vec; //定义一个储存value的数组
    void traversal(TreeNode* root){
        if(root==nullptr) return; //如果为空，一定是二叉搜索树
        //采用左中右的方法，BST的中序遍历是单调递增的val
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }

    bool isValidBST(TreeNode* root) {
        traversal(root); //制作数组
        for(int i = 1; i < vec.size(); i++){
            if(vec[i] <= vec[i-1]) return false;
        }
        return true;
    }
};

class Solution {
public:
    //利用全局变量的递归法
    long long maxVal = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        //左中右
        //左
        bool left = isValidBST(root->left);
        //中 每次让遍历的前一个和当前遍历的那个值进行比较
        if(maxVal < root->val) maxVal = root->val;
        else return false;
        //右
        bool right = isValidBST(root->right);
        return left&&right; //当左右均为true时候才证明是BST
    }
};

class Solution {
public:
    //利用双指针的递归法
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        //左中右
        //左
        bool left = isValidBST(root->left);
        //中 每次让遍历的前一个和当前遍历的那个值进行比较
        if(pre!=nullptr && pre->val >= root->val) return false;
        pre = root; //记录前一个结点
        //右
        bool right = isValidBST(root->right);
        return left&&right; //当左右均为true时候才证明是BST
    }
};

class Solution {
public:
    //迭代法
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root; //记录当前节点
        TreeNode* pre = nullptr; //记录前一个结点
        while(cur!=nullptr || !st.empty()){
            //左
            if(cur!=nullptr){
                st.push(cur);
                cur = cur->left;
            }
            else{
                cur = st.top(); //中
                st.pop();
                if(pre!=nullptr && cur->val <= pre->val) return false;
                pre = cur;
                cur = cur->right; //右
            }
        }
        return true;
    }
};