617、合并二叉树
递归法：
class Solution {
public:TreeNode* traversal(TreeNode* root1, TreeNode* root2) {if(root1 == NULL && root2 == NULL) {return NULL;}else if(root1 == NULL) {return root2;}else if(root2 == NULL) {return root1;}root1->val = root1->val + root2->val;root1->left = traversal(root1->left, root2->left);root1->right = traversal(root1->right, root2->right);return root1;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {TreeNode* tem = traversal(root1, root2);return tem;}
};
迭代法：
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 == NULL) return root2;if(root2 == NULL) return root1;queue<TreeNode*> que;que.push(root1);que.push(root2);while(!que.empty()) {TreeNode* tem1 = que.front();que.pop();TreeNode* tem2 = que.front();que.pop();tem1->val = tem1->val + tem2->val;if(tem1->left != NULL && tem2->left != NULL) {que.push(tem1->left);que.push(tem2->left);}if(tem1->right != NULL && tem2->right != NULL) {que.push(tem1->right);que.push(tem2->right);}if(tem1->left == NULL && tem2->left != NULL) {tem1->left = tem2->left;}if(tem1->right == NULL && tem2->right != NULL) {tem1->right = tem2->right;}}return root1;}
};
700、二叉搜索树中的搜索
递归法：
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == NULL) {return NULL;}else if(root->val == val) {return root;}else if(root->val > val) {return searchBST(root->left, val);}else {return searchBST(root->right, val);}}
};
迭代法：
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while(root != NULL) {if(root->val == val) {return root;}else if(root->val > val) {root = root->left;}else if(root->val < val) {root = root->right;}}return NULL;}
};
98、验证二叉搜索树
递归法：
class Solution {
public:long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == NULL) return true;bool left = isValidBST(root->left);if(maxVal >= root->val) {return false;}else {maxVal = root->val;}bool right = isValidBST(root->right);return left && right;}
};
迭代法：
class Solution {
public:bool isValidBST(TreeNode* root) {if(root == NULL) return true;stack<TreeNode*> sta;TreeNode* cur = root;TreeNode* pre = NULL;while(cur != NULL || !sta.empty()) {while(cur != NULL) {sta.push(cur);cur = cur->left;}cur = sta.top();sta.pop();if(pre != NULL && pre->val >= cur->val) {return false;}else {pre = cur;}cur = cur->right;}return true;}
};
