一、二叉搜索树的应用
1. 700【二叉搜索树中的搜索】
- 题目： 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
- 代码：
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root==null) return null;if(root.val==val) return root;if(root.val > val){root = searchBST(root.left,val);}else {root = searchBST(root.right,val);}return root;}
}
2. 98【验证二叉搜索树】
- 题目： 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
- 代码：
class Solution {public boolean isValidBST(TreeNode root) {List<Integer> inorder = new LinkedList<>();traversal(root,inorder);for (int i = 1; i < inorder.size(); i++) {if(inorder.get(i-1)>=inorder.get(i)){return false;}}return true;}public void traversal(TreeNode root,List<Integer> inorder){if(root == null) return;traversal(root.left,inorder);inorder.add(root.val);traversal(root.right,inorder);}
}
3. 530【二叉搜索树的最小绝对差】
- 题目： 给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
- 代码：
class Solution {public int min = Integer.MAX_VALUE;public TreeNode pre;public int getMinimumDifference(TreeNode root) {traversal(root);return min;}public void traversal(TreeNode root){if(root == null) return;traversal(root.left);if(pre != null){int sub = Math.abs(pre.val-root.val);min = sub>min ? min:sub;}pre = root;traversal(root.right);}
}
4. 501【二叉搜索树中的众数】
- 题目： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
- 代码：
class Solution {public TreeNode pre = null;public int count = 0;public int max = 0;public int[] findMode(TreeNode root) {ArrayList<Integer> list = new ArrayList<>();traversal(root,list);int[] ansList = new int[list.size()];for (int i = 0; i < list.size(); i++) {ansList[i] = list.get(i);}return ansList;}public void traversal(TreeNode root,ArrayList<Integer> list){if(root == null) return;traversal(root.left, list);if(pre==null || pre.val!=root.val){count = 1;}else{count++;}if(count > max){max = count;list.clear();list.add(root.val);}else if(count == max){list.add(root.val);}pre = root;traversal(root.right,list);}
}
5. 701【二叉搜索树中的插入操作】
- 题目： 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。 - 代码：
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null){return new TreeNode(val);}if(root.val>val){root.left = insertIntoBST(root.left,val);}if(root.val<val){root.right = insertIntoBST(root.right,val);}return root;}
}
6. 450【删除二叉搜索树中的节点】
- 题目： 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤： - 代码：
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return root;if(root.val == key){if(root.left==null && root.right!=null){return root.right;}else if(root.left!=null && root.right==null){return root.left;}else if(root.left==null && root.right==null){return null;}else{TreeNode node = root.right;while (node.left!=null){node = node.left;}node.left = root.left;return root.right;}}if(root.left!=null) root.left = deleteNode(root.left,key);if(root.right!=null) root.right = deleteNode(root.right,key);return root;}
}
7. 669【修剪二叉搜索树】
- 题目： 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。 - 代码：
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return root;if(root.val<low){return trimBST(root.right,low,high);}else if(root.val>high){return trimBST(root.left,low,high);}root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}
}
8. 108【将有序数组转换为二叉搜索树】
- 题目： 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡二叉搜索树。
高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 - 代码：
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal(nums,0,nums.length);}public TreeNode traversal(int[] nums, int left, int right){if(left>=right){return null;}int mid = left+(right-left)/2;TreeNode node = new TreeNode(nums[mid]);node.left = traversal(nums,left,mid);node.right = traversal(nums,mid+1,right);return node;}
}
9. 538【把二叉搜索树转换为累加树】
- 题目： 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
- 代码：
class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {traversal(root);return root;}public void traversal(TreeNode root){if(root == null) return;traversal(root.right);sum += root.val;root.val = sum;traversal(root.left);}
}
二、树与回溯
1. 257【二叉树的所有路径】
- 题目： 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点 - 代码：
class Solution {List<String> ansList = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {if(root == null) return new ArrayList<>();String path = "";traversal(root,path);return ansList;}public void traversal(TreeNode root,String path){if(root.left == null && root.right == null){path = path + root.val;ansList.add(path);return;}String s = path + root.val+"->";if(root.left != null) traversal(root.left,s);if(root.right != null) traversal(root.right,s);}
}
2. 112【路径总和】
- 题目： 给你二叉树的根节点 root 和一个表示目标和的整数targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
- 代码：
class Solution {HashSet<Integer> sums = new HashSet<>();public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null) return false;traversal(root,0);if(sums.contains(targetSum)){return true;}return false;}public void traversal(TreeNode root, int sum){if(root.left==null && root.right==null){sum += root.val;sums.add(sum);return;}sum += root.val;if(root.left!=null) traversal(root.left,sum);if(root.right!=null) traversal(root.right,sum);}
}
3. 113【路径总和Ⅱ】
- 题目： 给你二叉树的根节点root和一个整数目标和targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
- 代码：
class Solution {List<List<Integer>> ansList = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root == null) return new ArrayList<>();traversal(root,targetSum);return ansList;}public void traversal(TreeNode root, int targetSum){path.add(root.val);targetSum -= root.val;if(root.left==null && root.right==null){if(targetSum == 0){ansList.add(new ArrayList<>(path));}return;}if(root.left != null) {traversal(root.left,targetSum);path.removeLast();}if(root.right != null) {traversal(root.right,targetSum);path.removeLast();}}
}
4. 236【二叉树的最近公共祖先】
- 题目： 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” - 代码：
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null || 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 right;if(left!=null && right==null) return left;if(left==null && right==null) return null;return root;}
}
5. 235【二叉搜索树的最近公共祖先】
- 题目： 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
- 代码：
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){TreeNode node = lowestCommonAncestor(root.left,p,q);}if(root.val<p.val && root.val<q.val){TreeNode node = lowestCommonAncestor(root.right,p,q);}return root;}
}
