二叉树-LeetCode 235、236、226、230（中序，LCA，DFS）
二叉树-LeetCode 235、236、226、230（中序，LCA，DFS）
二叉树：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/