此博客主要记录BST（Binary Search Tree）
一、修剪二叉查找树
669.修建二叉搜索树 （medium） 2021-07-06
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
使用递归的方法
class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if(root == null) return null; if(root.val > high) return trimBST(root.left, low, high); if(root.val < low) return trimBST(root.right, low, high); root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } }
二、寻找二叉查找树的第k小的元素
230.二叉搜索树中第k小的元素 （medium） 2021-07-07
给定一个二叉搜索树的根节点root ，和一个整数k ，请你设计一个算法查找其中第k 个最小的元素（从1开始计数）。
class Solution { public int kthSmallest(TreeNode root, int k) { int kthSmall = -1; Stack<TreeNode> stack = new Stack<>(); TreeNode node = root; int count = 0; while(!stack.isEmpty() || node != null){ while(node != null){ stack.push(node); node = node.left; } TreeNode node_out = stack.pop(); count++; if(count == k){ kthSmall = node_out.val; break; } node = node_out.right; } return kthSmall; } }
三、把二叉查找树每个节点的值都加上比他大的节点的值
538. 把二叉搜索树转换为累加树（medium） 2021-07-07
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点
node的新值等于原树中大于或等于node.val的值之和。提醒一下，二叉搜索树满足下列约束条件：
-
-
节点的左子树仅包含键 小于 节点键的节点。
-
节点的右子树仅包含键 大于 节点键的节点。
-
左右子树也必须是二叉搜索树。
-
我的做法虽然有用但是很傻，常规解法，首先遍历得到所有节点的累加和，然后再次遍历一遍修改各个节点的值。
class Solution { public TreeNode convertBST(TreeNode root) { sum = inOrderSum(root); return inOrder(root); } //对二叉搜索树进行求和 int sum = 0; public int inOrderSum(TreeNode root){ if(root == null) return -1; inOrderSum(root.left); sum = sum + root.val; inOrderSum(root.right); return sum; } //对二叉树进行前序遍历，然后修改节点的值 int preSum = 0; public TreeNode inOrder(TreeNode root){ if(root == null) return null; inOrder(root.left); int temp = root.val; root.val = sum - preSum; preSum = preSum + temp; inOrder(root.right); return root; } }
在二叉搜索树中我一直执着于中序遍历，但是这个题使用（右子树 -> 根节点 -> 左子树） 显然更方便。一次遍历就行，时间空间都暴打我的方法。
public TreeNode convertBST(TreeNode root) { traver(root); return root; } private void traver(TreeNode node) { if (node == null) return; traver(node.right); sum += node.val; node.val = sum; traver(node.left); }
四、二叉查找树的最近公共祖先
235.二叉搜索树的最近公共祖先 （easy） 2021-07-07
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
这个题我一点头绪都没有，答案只需要三行就解决了，破防了。
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; }
五、二叉树最近的公共祖先
236. 二叉树最近的公共祖先 （medium） 2021-07-07
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
这个题和上面的题极其相似，难度增加，但是我依然没有头绪。
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return null; if(root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if(left != null && right != null) return root; if(left != null) return left; if(right != null) return right; return null; } }
六、从有序数组中构造二叉查找树
108.将有序数组转换成二叉搜索树 （easy） 2021-07-07
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
class Solution { public TreeNode sortedArrayToBST(int[] nums) { int len = nums.length; return sortedArrayToBST(nums, 0, len - 1); } //这个函数的作用是将从l 到 r 的下标的数组进行整理 public TreeNode sortedArrayToBST(int[] nums, int l, int r){ if(l > r) return null; int m = l + (r - l) / 2; TreeNode root = new TreeNode(nums[m]); root.left = sortedArrayToBST(nums, l , m - 1); root.right = sortedArrayToBST(nums, m + 1, r); return root; } }
七、根据有序链表构造平衡二叉查找树
109. 有序链表转换二叉搜索树 （medium） 2021-07-07
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
我用数组的思路去解这个题，用时击败 5%的用户。
评论里说到，思想的懒惰不利于写出牛逼的程序，我深以为然。
class Solution { public TreeNode sortedListToBST(ListNode head) { ListNode node = head; int count = 0; //链表的长度 while(node != null){ count ++; node = node.next; } return toBST(head, 0, count - 1); } public TreeNode toBST(ListNode head, int l, int r){ if(l > r) return null; int m = l + (r - l) / 2; TreeNode root = new TreeNode(searchList(head, m)); root.left = toBST(head, l, m - 1); root.right = toBST(head, m + 1, r); return root; } //寻找链表中下标为m 的元素, m小于链表的长度 public int searchList(ListNode head, int m){ ListNode node = new ListNode(); node.next = head; for(int i = 0; i <= m; i++){ node = node.next; } return node.val; } }
碰到链表找中点的算法，使用快慢指针，让快的指针一次移动两格，慢的一次一格。当快指针到队尾的时候，慢指针正好是在链表中间。
链表相对于数组有自己的优势，其不需要记录数组的下标，只需要将链表断开就行。
转换思路，用时击败 100%
class Solution { public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; if(head.next == null) return new TreeNode(head.val); ListNode fastNode = head; ListNode slowNode = head; ListNode midLeftNode = head; while(fastNode != null && fastNode.next != null){ fastNode = fastNode.next.next; midLeftNode = slowNode; slowNode = slowNode.next; } TreeNode root = new TreeNode(slowNode.val); midLeftNode.next = null; //将中间节点的左边节点的next指针置为null root.left = sortedListToBST(head); root.right = sortedListToBST(slowNode.next); return root; } }
八、在二叉查找树中寻找两个节点，使它们的和为一个定值
653. 两数之和IV （ BST） （easy） 2021-07-07
给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
思想需要简单，将二叉查找树中序遍历为有序列表，然后对列表进行查找。
class Solution { public boolean findTarget(TreeNode root, int k) { List<Integer> l = TreeToList(root); int i = 0; int j = l.size() - 1; while(i < j){ int sum = l.get(i) + l.get(j); if(sum == k) return true; if(sum > k){ j--; }else{ i++; } } return false; } List<Integer> list = new ArrayList<>(); public List<Integer> TreeToList(TreeNode root){ if(root == null) return null; TreeToList(root.left); list.add(root.val); TreeToList(root.right); return list; } }