今日内容:
● 235. 二叉搜索树的最近公共祖先
● 701.二叉搜索树中的插入操作
● 450.删除二叉搜索树中的节点
详细布置
235. 二叉搜索树的最近公共祖先
相对于 二叉树的最近公共祖先 本题就简单一些了,因为 可以利用二叉搜索树的特性。
视频讲解:https://www.bilibili.com/video/BV1Zt4y1F7ww
class Solution { TreeNode left; TreeNode right; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root.val > p.val && root.val > q.val) { left = lowestCommonAncestor(root.left, p, q); if (left != null) { return left; } } if (root.val < p.val && root.val < q.val) { right = lowestCommonAncestor(root.right, p, q); if (right != null) { return right; } } return root; } }
701.二叉搜索树中的插入操作
本题比想象中的简单,大家可以先自己想一想应该怎么做,然后看视频讲解,就发现 本题为什么比较简单了。
视频讲解:https://www.bilibili.com/video/BV1Et4y1c78Y
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { // 如果当前节点为空,也就意味着val找到了合适的位置,此时创建节点直接返回。 if (root == null) { return new TreeNode(val); } if (root.val < val) { root.right = insertIntoBST(root.right, val);// 递归创建右子树 } else if (root.val > val) { root.left = insertIntoBST(root.left, 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; } }
450.删除二叉搜索树中的节点
相对于 插入操作,本题就有难度了,涉及到改树的结构
视频讲解:https://www.bilibili.com/video/BV1tP41177us
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; } }标签:right,TreeNode,val,root,二叉,搜索,return,树中,left From: https://www.cnblogs.com/gaoyuan2lty/p/17048322.html