一、二叉搜索樹的應用

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;}
}