二叉树:LeetCode #235 236 226 230
1
编程题
【LeetCode #235】二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
解题思路:
整体思路为,根据二叉搜索树的特性,当p、q节点的值均大于root节点的值,那么其LCA一定在root的右子树中,反之则在root的左子树中,如果root->val在p->val和q->val之间,则返回root为p、q的LCA.
(递归法)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left, p, q);
if(p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right, p, q);
return root;
}
};
(迭代法)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root != NULL){
if(root->val > p->val && root->val > q->val){
root = root->left;
continue;
}
if(root->val < p->val && root->val < q->val){
root = root->right;
continue;
}
return root;
}
return NULL;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
【LeetCode #236】二叉树的最近公共祖先
解题思路
递归法:遍历二叉树的每个节点,判断该节点对应的左右子树,如果子树不含有p或者q,则返回nullptr, 否则,如果p和q分别位于该节点的左右子树,即left,right都不为nullptr,则返回当前节点root,如果p和q都在左子树或者都在右子树,则返回来自左边或右边的LCA。
迭代法:使用DFS的方法找到一条通向p的路径,以及一条通向q的路径,并保存路径的值。然后遍历查询(找到两条路径最后一个相同的值),即得到最近的公共节点!
(递归法)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || p == root || q == root)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left != nullptr && right != nullptr)
return root;
else if(left != nullptr)
return left;
else if(right != nullptr)
return right;
return nullptr;
}
};
(迭代法)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
bool dfs(vector<TreeNode*>& path, TreeNode* node, TreeNode* find) {
if (node == nullptr) return false;
path.push_back(node);
if (node == find) {
return true;
}
if(dfs(path, node->left, find)) return true;
if(dfs(path, node->right, find)) return true;
path.pop_back();
return false;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> ll, rr;
if(!dfs(ll, root, p) || !dfs(rr, root, q)) return nullptr;
int i = ;
for (; i < ll.size() && i < rr.size(); i++) {
if (ll[i] != rr[i]) return ll[i-1];
}
return ll[i-1];
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
【LeetCode #226】翻转二叉树
解题思路:
主要思路是对每个节点root的左右子节点root->left, root->right 的数值进行交换即可!然后讲这样的变换遍历到整个二叉树的所有节点!
(递归法)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr){
return root;
}else{
TreeNode* tmp = root->right;
root->right = root->left;
root->left = tmp;
root->left = invertTree(root->left);
root->right = invertTree(root->right);
}
return root;
}
};
(迭代法,层次遍历)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) return nullptr;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* node = que.front();
que.pop();
TreeNode* tmp = node->right;
node->right = node->left;
node->left = tmp;
if(node->left != nullptr) que.push(node->left);
if(node->right != nullptr) que.push(node->right);
}
return root;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/invert-binary-tree
【LeetCode #230】二叉搜索树中第K小的元素
解题思路:
对于二叉搜索树来说,其中序遍历是一个从小到大单调递增的序列,因此对该二叉树进行中序遍历的第k个数,即为二叉搜索树中第K小的元素。
(递归法,中序遍历)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
void inorder(TreeNode* root, int &cnt, int &ans){
if(root == nullptr) return;
inorder(root->left, cnt, ans);
--cnt;
if(cnt == ){
ans = root->val;
return;
}
inorder(root->right, cnt, ans);
}
public:
int kthSmallest(TreeNode* root, int k) {
int cnt = k, ans = ;
inorder(root, cnt, ans);
return ans;
}
};
(迭代法,中序遍历)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*>sta;
int num = ;
TreeNode* cur = root;
while(!sta.empty() || cur != nullptr){
if(cur != nullptr){
sta.push(cur);
cur = cur->left;
}else{
cur = sta.top();
sta.pop();
num++;
if(num == k)
return cur->val;
cur = cur->right;
}
}
return ;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/