leetcode刷题-二叉树07

235. 二叉搜索树的最近公共祖先

代码随想录文档讲解
LeetCode

思路：

注意，这是二叉搜索树

1. 如果当前遍历到的节点比p和q都大的话，说明p、q及他们的公共祖先在这个节点的左子树里；

2. 如果当前遍历到的节点的值在p和q之间，那么说明它是它们的公共祖先，那是不是最近公共祖先？是的
   如下图所示，如果 从节点5继续向左遍历，那么将错过成为p的祖先， 如果从节点5继续向右遍历则错过成为q的祖先。所以当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。

伪代码c++：

// 递归法 
TreeNode traversal(cur, p, q){if(cur == NULL) return NULL;// 左if(cur->val > p->val && cur->val > q->val) {left = traversal(cur->left, p, q);if(left != NULL) return left;}// 右if(cur->val < p->val && cur->val < q->val){right = traversal(cur->right, p, q)if(right != NULL) return right;}// 剩下的情况当前数值在就是在p和q之间return cur;
}// 迭代法
while(cur){if(cur->val > p->val && cur->val > q->val) cur = cur->leftelse if()cur = cur->rightreturn cur
}

python代码：

# 解法一：递归法
class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root:return Noneif root.val > p.val and root.val > q.val:left = self.lowestCommonAncestor(root.left, p, q)if left: return leftelif root.val < p.val and root.val < q.val:right = self.lowestCommonAncestor(root.right, p, q)if right: return rightelse:return root
# 解法二：迭代法
class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':while root:if root.val > p.val and root.val > q.val:root = root.leftelif root.val < p.val and root.val < q.val:root = root.rightelse:return rootreturn None

701.二叉搜索树中的插入操作

leetcode题目链接
代码随想录文档讲解

思路：

不考虑二叉树的结构，其实插入任何一个节点都可以在叶子节点里找到它的位置
只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

伪代码（C++）：

TreeNode insert(root, val){if(root == NULL){TreeNode node = new TreeNode(val);return node;}if(val < root->val)root->left = insert(root->left, val);if(val > root->val)root->right = insert(root->right, val);return root;

python代码：

class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if not root:node = TreeNode(val)return nodeif root.val > val:root.left = self.insertIntoBST(root.left, val)elif root.val < val:root.right = self.insertIntoBST(root.right, val)return root

450.删除二叉搜索树中的节点

leetcode题目链接
代码随想录文档讲解

思路：

题目要求：删除二叉搜索树的节点之后还要求是一棵二叉搜索树
删除某个节点就不可避免地改变二叉树的结构了
五种情况：

1. 没找到删除的节点，遍历到空节点直接返回了
2. 删除的节点为叶子节点
3. 删除的节点 左不空 右空
4. 删除的节点 左空 右不空
5. 删除的节点 左不空右不空，这种情况最复杂，需要大幅修改二叉树的结构，如下图所示：

伪代码（C++）：

TreeNode* delete(root, key){// 第一种情况，没有找到值if(root==NULL) return NULL;// 剩下的情况，找到值了if(root->val == key){if(root->left==NULL && root->right==NULL) // 叶子节点return NULL;else if(root->left!=NULL && root->right==NULL) // 右为空return root->left;else if(root->left==NULL && root->right != NULL) // 左为空return root->right;else  // 都不为空{// 找到右子树最左边的节点cur = root->right;while(cur->left != NULL) cur = cur->left;cur->left = root->left;// 此时变成了左为空右不为空return root->right;}}if(root->val > key)root->left = delete(root->left, key)if(root->val << key)root->right = delete(root->right, key)return root;
}

python代码：

class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if not root:return Noneif root.val == key:if not root.left and not root.right:return Noneelif not root.left:return root.rightelif not root.right:return root.leftelse:cur = root.rightwhile cur.left:cur = cur.leftcur.left = root.leftreturn root.rightif root.val > key:root.left = self.deleteNode(root.left, key)if root.val < key:root.right = self.deleteNode(root.right, key)return root