LeetCode刷题笔记之二叉树（四）

一、二叉搜索树的应用

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) {//BST中序遍历是有序的，直接中序遍历二叉树，遇到空节点插入即可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) {//分为五种情况：//①未找到，直接返回root//②找到的节点左子树为空，右子树非空，右子树补上//③找到的节点右子树为空，左子树非空，左子树补上//④找到的节点左右子树都为空，直接删除//⑤找到的节点左右子树都非空，左子树添加到右子树最左边，右子树补上//或者右子树添加到左子树最右边，左子树补上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) {//要想构造一个平衡的BST，就需要在数组的中间位置开始进行构造//[left,right)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) {//找最近公共祖先，就需要从下往上找，也就是说要根据前序遍历二叉树//找到哪个节点就返回哪个节点//如果没找到就返回nullif(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) {//二叉搜索树的中序遍历是有序的，所以p,q的最近公共祖先一定在[p,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;}
}