怎样建立自己网站难吗,在线代理访问网站的网址,网络服务商的责任,深圳微信商城网站设计费用目录 二叉搜索树的最近公共祖先二叉搜索树中的插入操作删除二叉搜索树中的节点普通二叉树的删除方式 LeetCode 235. 二叉搜索树的最近公共祖先 LeetCode 701.二叉搜索树中的插入操作 LeetCode 450.删除二叉搜索树中的节点
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到… 目录 二叉搜索树的最近公共祖先二叉搜索树中的插入操作删除二叉搜索树中的节点普通二叉树的删除方式 LeetCode 235. 二叉搜索树的最近公共祖先 LeetCode 701.二叉搜索树中的插入操作 LeetCode 450.删除二叉搜索树中的节点
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
如果 中间节点是 q 和 p 的公共祖先那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 p 中节点 q 或者 中节点 q 中节点 p。
且当我们从上向下去递归遍历第一次遇到 cur节点是数值在[q, p]区间中那么cur就是 q和p的最近公共祖先。
p、q 为不同节点且均存在于给定的二叉搜索树中。→ 省去了判断是否为 null 的操作。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// if (root null) return root; // 因为p、q 为不同节点且均存在于给定的二叉搜索树中所以不用判断// TreeNode left lowestCommonAncestor(root.left, p, q); if (left ! null) return left; // 因为p、q 为不同节点且均存在于给定的二叉搜索树中所以不用判断if (root.val p.val root.val q.val) return lowestCommonAncestor(root.left, p, q);if (root.val p.val root.val q.val) return lowestCommonAncestor(root.right, p, q);return root;}
}class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (true) {if (root.val p.val root.val q.val) {root root.left;} else if (root.val p.val root.val q.val) {root root.right;} else {break;}}return root;}
}二叉搜索树中的插入操作
给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。
注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
只要遍历二叉搜索树找到空节点 插入元素就可以了。
终止条件就是找到遍历的节点为null的时候就是要插入节点的位置了并把插入的节点返回。
这里把添加的节点返回给上一层就完成了父子节点的赋值操作了。
把新的节点返回给上一层上一层就要用 root-left 或者 root-right接住
class Solution {TreeNode pre null;TreeNode cur null;public TreeNode insertIntoBST(TreeNode root, int val) {if (root null) {TreeNode node new TreeNode(val);return node;}if (root.val val) root.left insertIntoBST(root.left, val);if (root.val val) root.right insertIntoBST(root.right, val);return root;}}class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root null) return new TreeNode(val);TreeNode newRoot root;TreeNode pre root;while (root ! null) {pre root;if (root.val val) {root root.left;} else if (root.val val) {root root.right;}}if (pre.val val) {pre.left new TreeNode(val);} else {pre.right new TreeNode(val);}return newRoot;}
}删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。
一般来说删除节点可分为两个步骤
首先找到需要删除的节点 如果找到了删除它。 二叉搜索树中删除节点遇到的情况 没找到删除的节点遍历到空节点直接返回 找到删除的节点 2.1 左右孩子都为空叶子节点 直接删除节点返回 null 为根节点 2.2 删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点 2.3 删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点 2.4 左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root null) return root; // 第一种情况没找到删除的节点遍历到空节点直接返回了if (root.val key) { // 内含第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点if (root.left null) { // 第三种情况其左孩子为空右孩子不为空删除节点右孩子补位 返回右孩子为根节点return root.right;} else if (root.right null) { // 第四种情况其右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点return root.left;} else {// 第五种情况左右孩子节点都不为空则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。TreeNode cur root.right; // 找右子树最左面的节点while (cur.left ! null) {cur cur.left;}cur.left root.left; // 把要删除的节点root左子树放在cur的左孩子的位置root root.right; // 返回旧root的右孩子作为新rootreturn root;}}if (root.val key) root.left deleteNode(root.left, key);if (root.val key) root.right deleteNode(root.right, key);return root;}
}二叉搜索树添加节点只需要在叶子上添加就可以的不涉及到结构的调整而删除节点操作涉及到结构的调整。
普通二叉树的删除方式
普通二叉树的删除方式没有使用搜索树的特性遍历整棵树用交换值的操作来删除目标节点。
代码中目标节点要删除的节点被操作了两次
第一次是和目标节点的右子树最左面节点交换。
第二次直接被NULL覆盖了。
class Solution {public TreeNode deleteNode(TreeNode root, int key) {root delete(root,key);return root;}private TreeNode delete(TreeNode root, int key) {if (root null) return null;if (root.val key) {root.left delete(root.left,key);} else if (root.val key) {root.right delete(root.right,key);} else {if (root.left null) return root.right;if (root.right null) return root.left;TreeNode tmp root.right;while (tmp.left ! null) {tmp tmp.left;}root.val tmp.val;root.right delete(root.right,tmp.val);}return root;}
}
