二叉搜索树的最近公共祖先 删除二叉搜索树中的节点 修剪二叉搜索树(Java)

二叉搜索树的最近公共祖先(Java)

重要结论：第一次遇到cur节点是数值在[q, p]区间中，那么cur就是q和p的最近公共祖先（闭区间是因为公共祖先可以是本身）
(如果知道这个结论：本题就类似于给定二叉搜索树（BST）的根节点 root 和一个整数值 val—第700题)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null){return null;}if(root.val >= p.val && root.val <= q.val || (root.val >= q.val && root.val <= p.val)){return root;}else if(root.val > p.val && root.val > q.val){return lowestCommonAncestor(root.left, p, q);}else{return lowestCommonAncestor(root.right, p, q); //找到就是root,没找到就是null}}
}

删除二叉搜索树中的节点(Java)

大体框架：寻找是否有该节点。
细节：找到该节点后判断以下几种情况：

• 左右孩子都为空：直接删除节点
• 其无左子：其右子顶替其位置，删除了该节点；
• 其无右子：其左子顶替其位置，删除了该节点；
• 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) { if(root == null){return null;}if(root.val == key){if(root.left == null && root.right == null){ //1：都为空直接删除return null;}else if(root.left == null || root.right == null){ // 2. 一侧为空，返回另一侧return root.left == null ? root.right : root.left;}else{ //3：左右两侧都有值TreeNode node = root.right;while(node.left != null){node = node.left; //不断寻找最左节点}node.left = root.left; // 把左节点放在右节点的最左节点的左边；return root.right;}}else if(root.val > key){root.left = deleteNode(root.left, key);}else{root.right = deleteNode(root.right, key);}return root;}
}

修剪二叉搜索树(Java)

• 若 root.val 小于边界值 low，则 root 的左子树必然均小于边界值，我们递归处理 root.right 即可；
• 若 root.val 大于边界值 high，则 root 的右子树必然均大于边界值，我们递归处理 root.left 即可；
• 若 root.val 符合要求，则 root 可被保留，递归处理其左右节点并重新赋值即可。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null){return null;}if(root.val < low){return  trimBST(root.right, low, high);}else if(root.val > high){return trimBST(root.left, low, high);}else{root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}
}

写博客的目的是每日督促并记录刷题，也欢迎大家批评指正~（day22）