617. 合并二叉樹(shù)
你兩棵二叉樹(shù)： root1 和 root2 。
想象一下垫桂，當(dāng)你將其中一棵覆蓋到另一棵之上時(shí)师幕，兩棵樹(shù)上的一些節(jié)點(diǎn)將會(huì)重疊（而另一些不會(huì)）。你需要將這兩棵樹(shù)合并成一棵新二叉樹(shù)诬滩。合并的規(guī)則是：如果兩個(gè)節(jié)點(diǎn)重疊霹粥，那么將這兩個(gè)節(jié)點(diǎn)的值相加作為合并后節(jié)點(diǎn)的新值；否則疼鸟，不為 null 的節(jié)點(diǎn)將直接作為新二叉樹(shù)的節(jié)點(diǎn)后控。
返回合并后的二叉樹(shù)。
注意: 合并過(guò)程必須
從兩個(gè)樹(shù)的根節(jié)點(diǎn)開(kāi)始空镜。
示例 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;
//這兩步是關(guān)鍵代碼
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;
}
};
注意點(diǎn)：
- 注意當(dāng)節(jié)點(diǎn)為空時(shí)浩淘，直接返回不為空的節(jié)點(diǎn)
700. 二叉搜索樹(shù)中的搜索
給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn) root 和一個(gè)整數(shù)值 val。
你需要在 BST 中找到節(jié)點(diǎn)值等于 val 的節(jié)點(diǎn)姑裂。 返回以該節(jié)點(diǎn)為根的子樹(shù)馋袜。 如果節(jié)點(diǎn)不存在，則返回 null 舶斧。
示例 1:
輸入：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);
}
};
二叉樹(shù)遍歷
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
stack<TreeNode*> st;
TreeNode* cur = root;
while(!st.empty() || cur != nullptr) {
if (cur != nullptr) {
// 要先push再賦值欣鳖。要不然會(huì)把空值放到棧里頭
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
if (cur->val == val) {
return cur;
}
cur = cur->right;
}
}
return nullptr;
}
};
注意點(diǎn)：
1.看到搜索樹(shù)，一般都先想到中序遍歷茴厉。中序遍歷只有一層循環(huán)Ｔ筇āＪ踩佟！怀酷！沒(méi)有兩層
2.中序遍歷的結(jié)束條件要搞清楚 ５九馈！
3.遍歷左樹(shù)的時(shí)候蜕依，一定要先push再賦值ＮΤ！要不然會(huì)有空值放在棧里頭Ｑ摺友瘤！
迭代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;
}
};
注意點(diǎn)：
1.也是利用二叉搜索樹(shù)的性質(zhì)
98. 驗(yàn)證二叉搜索樹(shù)
給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ，判斷其是否是一個(gè)有效的二叉搜索樹(shù)檐束。
注意點(diǎn)：
1.還是中序遍歷二叉搜索樹(shù)
2.注意點(diǎn)同上辫秧。中序遍歷的循環(huán)結(jié)束條件，和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) {
// 中序遍歷只有一次循環(huán)Ｃ讼贰！Ｉ稹柿究！不要嵌套兩次循環(huán)！８襦摇笛求！循環(huán)條件while和循環(huán)內(nèi)的判斷條件！糕簿！
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); // 將二叉搜索樹(shù)轉(zhuǎn)換為有序數(shù)組
traversal(root->right);
}
public:
bool isValidBST(TreeNode* root) {
vec.clear(); // 不加這句在leetcode上也可以過(guò)探入，但最好加上
traversal(root);
for (int i = 1; i < vec.size(); i++) {
// 注意要小于等于，搜索樹(shù)里不能有相同元素
if (vec[i] <= vec[i - 1]) return false;
}
return true;
}
};
