如何免费做网站域名,wordpress 赚钱,启业网查询官网,摄影网站开发的背景系列文章目录 目录 系列文章目录235. 二叉搜索树的最近公共祖先①递归法自己写的简洁版 ②迭代法不能这样写#xff01;正确写法 701.二叉搜索树中的插入操作①递归法②迭代法 450.删除二叉搜索树中的节点递归法 235. 二叉搜索树的最近公共祖先
①递归法
自己写的
class So…系列文章目录 目录 系列文章目录235. 二叉搜索树的最近公共祖先①递归法自己写的简洁版 ②迭代法不能这样写正确写法 701.二叉搜索树中的插入操作①递归法②迭代法 450.删除二叉搜索树中的节点递归法 235. 二叉搜索树的最近公共祖先
①递归法
自己写的
class Solution {TreeNode result;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//终止条件if (root null || root p || root q) return root;if (root.val p.val root.val q.val) {result lowestCommonAncestor(root.left,p,q);} else if (root.val p.val root.val q.val) {result lowestCommonAncestor(root.right,p,q);} else {return root;}return result;}
}简洁版
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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;}
}②迭代法
不能这样写 图片来自热心网友大佬
5和6的最近公共祖先是8而不是4。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {while (root.val p.val root.val q.val) root root.left;while (root.val p.val root.val q.val) root root.right;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;}
}701.二叉搜索树中的插入操作
①递归法
递归三部曲
确定递归函数参数以及返回值参数就是根节点指针以及要插入元素这里递归函数要不要有返回值呢可以有也可以没有但递归函数如果没有返回值的话实现是比较麻烦的下面也会给出其具体实现代码。有返回值的话可以利用返回值完成新加入的节点与其父节点的赋值操作。确定终止条件终止条件就是找到遍历的节点为null的时候就是要插入节点的位置了并把插入的节点返回。确定单层递归的逻辑 如果root.val val说明应该将val插入左子树 如果左子树不存在将val作为root.left如果左子树存在让左子树插入val 如果root.val val说明应该将val插在右子树 如果右子树不存在将val作为root.right如果右子树存在让右子树插入val 返回插入val后的根节点即左右子树插入节点后的根节点。
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {//终止条件if (root null) return new TreeNode(val);if (root.val val) {root.leftinsertIntoBST(root.left, val);} else if (root.val val) {root.rightinsertIntoBST(root.right, val);}return root;}
}②迭代法
迭代法遍历的过程中需要记录一下当前遍历的节点的父节点这样才能做插入节点的操作。用pre指针来记录上一个节点。
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root null) return new TreeNode(val); // root为空直接插入后返回TreeNode newRoot root;//记录根节点TreeNode pre null;// 这个很重要需要记录上一个节点否则无法赋值新节点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;}
}450.删除二叉搜索树中的节点
二叉搜素树的性质
左子树的所有val值 当前节点的val值 右子树的最小val值 右子树的最左边节点的val值。
递归法
递归三部曲
确定递归函数参数以及返回值通过递归返回值删除节点。确定终止条件删除当前节点的逻辑放在终止条件中二叉搜索树中删除节点有以下五种情况 第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点的右子树第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点的左子树第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点的右节点作为删除后树的根节点。
注终止条件可以简化为 if (root null) return root;//找不到要删除的节点返回nullif (root.val key) {if (root.left null) {return root.left;} else if (root.right null) {return root.right;} else {TreeNode cur root.right;while (cur.left ! null) {cur cur.left;}cur.left root.left;return root.right;}}其中当要删除的节点的左右子树都不为空一直循环找到右子树最左边的节点时注意判断条件必须为while (cur.left ! null) 而不能是while (cur ! null) 否则会在cur.left root.left;这里报空指针异常。
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//终止条件if (root null) return root;//找不到要删除的节点返回nullif (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 {//左右子树都不为空TreeNode cur root.right;while (cur.left ! null) {//一直循环找到右子树最左边的节点cur cur.left;}cur.left root.left;//将要删除的节点的左子树拼接到右子树最左边的节点return root.right;//返回要删除的节点右子树}}// 如果root.val key证明要删除的节点应该会出现在左子树上获取左子树删除key节点后的根节点作为新的左节点if (root.val key) root.left deleteNode(root.left, key);// 如果root.val key证明要删除的节点应该会出现在右子树上获取右子树删除key节点后的根节点作为新的右节点if (root.val key) root.right deleteNode(root.right, key);// 返回删除key节点后的根节点return root;}
}
