617. 合并二叉树

你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

merge.jpg

从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

class Solution {
public:
    //TreeNode* buildNewTrees(TreeNode* root1, TreeNode* root2)
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //TreeNode* newNode = new TreeNode();
        if (root1 == nullptr && root2 == nullptr) return nullptr;
//这两步是关键代码
        if (root1 == nullptr) {
            return root2;
        }
        if (root2 == nullptr) {
            return root1;
        }
        root1->val = root1->val + root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

注意点：

1. 注意当节点为空时，直接返回不为空的节点

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
示例 1:

tree1 (1).jpg

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

递归

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return root;
        if (root->val == val) return root;
        if (root->left == nullptr && root->right == nullptr) return nullptr;
        if (root->val < val) return searchBST(root->right, val);
        return searchBST(root->left, val);
    }
};

二叉树遍历

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                // 要先push再赋值。要不然会把空值放到栈里头
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                if (cur->val == val) {
                    return cur;
                }
                cur = cur->right;
            }
        }
        return nullptr;
    }
};

注意点：

1.看到搜索树，一般都先想到中序遍历。中序遍历只有一层循环！！！！没有两层
2.中序遍历的结束条件要搞清楚 ！！
3.遍历左树的时候，一定要先push再赋值！！要不然会有空值放在栈里头！！

迭代2

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

注意点：
1.也是利用二叉搜索树的性质

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

注意点：

1.还是中序遍历二叉搜索树
2.注意点同上。中序遍历的循环结束条件，和push、cur赋值先后顺序

迭代

class Solution {
public:
    bool isValid(vector<int>& result) {
        if (result.size() <= 1) {
            return true;
        }
        for(int i = 0; i < result.size() - 1; i++) {
            if (result[i] >= result[i+1]) return false;
        }
        return true;
    }

    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> result;
        while (!st.empty() || cur != nullptr) {
            // 中序遍历只有一次循环！！！！不要嵌套两次循环！！！循环条件while和循环内的判断条件！！
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();     
                st.pop();           
                result.emplace_back(cur->val);
                cur = cur->right;
            }
        }
        return isValid(result);
    }
};

递归

class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};