動態代理和責任鏈設計模式適用範圍廣，在Spring和MyBatis有著重要的應用，比如SpringAOP、Mybatis的插件技術，想要搞懂當中的技術原理必須掌握上面兩個設計模式。 代理模式可以理解為您要操作一個對象，但是要經過這個對象的“代理”對象去操作。就好似你在一家軟體公司做開發，客戶發現程式 ...
二叉樹：
種類：滿二叉樹、完全二叉樹、二叉搜索樹、平衡二叉搜索樹
存儲方式：鏈式存儲、線式存儲（順序存儲）
二叉數遍歷：深度優先搜索（前序、中序、後序）：使用遞歸實現（實際用棧來實現）、迭代法（非遞歸的方式、棧），廣度優先搜索（層序遍歷）：用隊列
遞歸三步走寫法：1、確定遞歸函數的參數和返回值。2、確定終止條件。3、確定單層遞歸的邏輯。
144、二叉樹的前序遍歷
/**
* 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 List<Integer> preorderTraversal(TreeNode root) {
// List<Integer> result = new ArrayList<>();
// preorder(root, result);
// return result;
// }
// public void preorder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// result.add(root.val);
// preorder(root.left, result);
// preorder(root.right, result);
// }
// 方法二：非遞歸的方法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur != null){
result.add(cur.val);
stack.push(cur.right);
stack.push(cur.left);
}else{
continue;
}
}
return result;
}
// 方法三：統一風格的非遞歸
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
stack.push(cur);
stack.push(null);
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
145、二叉樹的後序遍歷
/**
* 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 List<Integer> postorderTraversal(TreeNode root) {
// List<Integer> result = new ArrayList<>();
// postOrder(root, result);
// return result;
// }
// public void postOrder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// postOrder(root.left, result);
// postOrder(root.right, result);
// result.add(root.val);
// }
// 方法二：非遞歸
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
result.add(cur.val);
if(cur.left != null){
stack.push(cur.left);
}
if(cur.right != null){
stack.push(cur.right);
}
}
Collections.reverse(result);
return result;
}
// 方法三：統一風格的非遞歸
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
stack.push(cur);
stack.push(null);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
94、二叉樹的中序遍歷
/**
* 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 List<Integer> inorderTraversal(TreeNode root) {
// List<Integer> result = new ArrayList<>();
// infixOrder(root, result);
// return result;
// }
// public void infixOrder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// infixOrder(root.left, result);
// result.add(root.val);
// infixOrder(root.right, result);
// }
// 方法二：非遞歸
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
// 方法三：統一風格的非遞歸
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null){
stack.push(cur.right);
}
stack.push(cur);
stack.push(null);
if(cur.left != null){
stack.push(cur.left);
}
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
廣度優先搜索：層序遍歷
102、二叉樹的層序遍歷
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<>();
int size = 0;
if(root != null){
queue.offer(root);
size = 1;
}
while(!queue.isEmpty()){
List<Integer> list1 = new ArrayList<>();
while(size > 0){
TreeNode cur = queue.poll();
list1.add(cur.val);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
list.add(list1);
}
return list;
}
}
107、二叉樹的層序遍歷 II
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
if(root != null){
queue.offer(root);
size = queue.size();
}
while(!queue.isEmpty()){
List<Integer> list1 = new ArrayList<>();
while(size > 0){
TreeNode cur = queue.poll();
list1.add(cur.val);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
list.add(list1);
}
Collections.reverse(list);
return list;
}
199、二叉樹的右視圖
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
int size = deque.size();
if(root != null){
deque.offer(root);
size = deque.size();
}
while(!deque.isEmpty()){
TreeNode cur = deque.peekLast();
resultList.add(cur.val);
while(size > 0){
cur = deque.poll();
if(cur.left != null){
deque.offer(cur.left);
}
if(cur.right != null){
deque.offer(cur.right);
}
size--;
}
size = deque.size();
}
return resultList;
}
}
637、二叉樹的層平均值
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> resultList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
Double sum = 0.0;
int count = 0;
if(root != null){
queue.offer(root);
size = queue.size();
}
while(!queue.isEmpty()){
count = size;
while(size > 0){
TreeNode cur = queue.poll();
sum += cur.val;
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
resultList.add(sum/count);
sum = 0.0;
size = queue.size();
}
return resultList;
}
}
429、N 叉樹的層序遍歷
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> resultList = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
int size = queue.size();
if(root != null){
queue.offer(root);
size = queue.size();
}
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
while(size > 0){
Node cur = queue.poll();
list.add(cur.val);
for(Node node: cur.children){
if(node != null){
queue.offer(node);
}
}
size--;
}
resultList.add(list);
size = queue.size();
}
return resultList;
}
}
515、在每個樹行中找最大值
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
if(root != null){
queue.offer(root);
size = queue.size();
}
int max = Integer.MIN_VALUE;
while(!queue.isEmpty()){
while(size > 0){
TreeNode cur = queue.poll();
max = max > cur.val ? max : cur.val;
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
resultList.add(max);
max = Integer.MIN_VALUE;
size = queue.size();
}
return resultList;
}
}
class Solution {
public Node connect(Node root) {
Queue<Node> queue = new LinkedList<>();
int size = 0;
if(root != null){
queue.offer(root);
size = queue.size();
}
while(!queue.isEmpty()){
while(size > 0){
Node temp = queue.poll();
if(size > 1){
temp.next = queue.peek();
}
if(temp.left != null){
queue.offer(temp.left);
}
if(temp.right != null){
queue.offer(temp.right);
}
size--;
}
size = queue.size();
}
return root;
}
}
117、填充每個節點的下一個右側節點指針 II
同上！
104、二叉樹的最大深度
![]
(https://img2022.cnblogs.com/blog/3018498/202211/3018498-20221121204402960-1570599807.png)
class Solution {
public int maxDepth(TreeNode root) {
return count(root, 0);
}
public int count(TreeNode root, int depth){
if(root == null){
return depth;
}
depth++;
return Math.max(count(root.left, depth),count(root.right, depth));
}
}
111、二叉樹的最小深度
class Solution {
public int minDepth(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
int depth = 0;
if(root != null){
queue.offer(root);
size = queue.size();
}
while(!queue.isEmpty()){
depth++;
while(size > 0){
TreeNode cur = queue.poll();
if(cur.left == null && cur.right == null){
return depth;
}
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
}
return depth;
}
}
226、翻轉二叉樹
/**
* 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 invertTree(TreeNode root) {
// Queue<TreeNode> queue = new LinkedList<>();
// int size = queue.size();
// if(root != null){
// queue.offer(root);
// size = queue.size();
// }
// while(!queue.isEmpty()){
// while(size > 0){
// TreeNode cur = queue.poll();
// if(cur.left != null){
// queue.offer(cur.left);
// }
// if(cur.right != null){
// queue.offer(cur.right);
// }
// swapChildren(cur);
// size--;
// }
// size = queue.size();
// }
// return root;
// }
// public void swapChildren(TreeNode cur){
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// 方法二：遞歸法，中序
// public TreeNode invertTree(TreeNode root) {
// if(root == null){
// return root;
// }
// invertTree(root.left);
// invertTree(root.right);
// swapChildren(root);
// return root;
// }
// public void swapChildren(TreeNode cur){
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// 方法三：迭代法：中序，統一風格
public TreeNode invertTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
stack.push(cur);
stack.push(null);
swapChildren(cur);
}else{
stack.pop();
stack.pop();
}
}
return root;
}
public void swapChildren(TreeNode cur){
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
}
}
589、N 叉樹的前序遍歷
class Solution {
// 方法一：遞歸
// public List<Integer> resultList = new ArrayList<>();
// public List<Integer> preorder(Node root) {
// if(root == null){
// return resultList;
// }
// resultList.add(root.val);
// for(Node node : root.children){
// preorder(node);
// }
// return resultList;
// }
// 方法二：迭代，統一風格
public List<Integer> preorder(Node root) {
List<Integer> resultList = new ArrayList<>();
Stack<Node> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
Node cur = stack.pop();
List<Node> list = new ArrayList<>();
list = cur.children;
for(int i = list.size() - 1; i >= 0; i--){
if(list.get(i) != null){
stack.push(list.get(i));
}
}
stack.push(cur);
stack.push(null);
}else{
stack.pop();
Node cur = stack.pop();
resultList.add(cur.val);
}
}
return resultList;
}
}
590、N 叉樹的後序遍歷
101、對稱二叉樹
class Solution {
// 方法一：遞歸，後序遍歷
// public boolean isSymmetric(TreeNode root) {
// return compare(root.left, root.right);
// }
// public boolean compare(TreeNode left, TreeNode right){
// if(left == null && right != null){
// return false;
// }
// if(right == null && left != null){
// return false;
// }
// if(right == null && left == null){
// return true;
// }
// if(left.val != right.val){
// return false;
// }
// boolean resultLeft = compare(left.left, right.right);
// boolean resultRight = compare(left.right, right.left);
// return resultLeft && resultRight;
// }
// 方法二：迭代
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()){
TreeNode left = deque.pollFirst();
TreeNode right = deque.pollLast();
if(left == null && right == null){
continue;
}
if(left == null && right != null){
return false;
}
if(left != null && right == null){
return false;
}
if(left.val != right.val){
return false;
}
deque.offerFirst(left.left);
deque.offerFirst(left.right);
deque.offerLast(right.right);
deque.offerLast(right.left);
}
return true;
}
}
559、N 叉樹的最大深度
class Solution {
public int maxDepth(Node root) {
return preOrder(root);
}
public int preOrder(Node root){
if(root == null){
return 0;
}
int depth = 0;
for(Node node : root.children){
depth = Math.max(depth, preOrder(node));
}
return depth + 1;
}
}
對稱二叉樹
二叉樹的最大深度
二叉樹的最小深度
完全二叉樹的節點個數
平衡二叉樹
二叉樹的所有路徑
404、左葉子之和
public int sumOfLeftLeaves(TreeNode root) {
if(root == null){
return 0;
}
int left = sumOfLeftLeaves(root.left);
int right = sumOfLeftLeaves(root.right);
int val = 0;
if(root.left != null && root.left.left == null &&root.left.right == null){
val = root.left.val;
}
int sum = left + right + val;
return sum;
}
}
513找樹左下角的值
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
int size = queue.size();
if(root != null){
queue.offer(root);
size = queue.size();
}
int find = 0;
while(!queue.isEmpty()){
Queue<TreeNode> result = new LinkedList<>();
while(size > 0){
TreeNode cur = queue.poll();
result.offer(cur);
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
size--;
}
size = queue.size();
find = result.peek().val;
}
return find;
}
}
112、路徑總和
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null){
return false;
}
List<Integer> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
pathSum(root, result, temp);
return result.contains(targetSum);
}
public void pathSum(TreeNode root, List<Integer> result, List<Integer> temp){
temp.add(root.val);
if(root.left == null && root.right == null){
int sum = 0;
for(int i = 0; i < temp.size(); i++){
sum += temp.get(i);
}
result.add(sum);
}
if(root.left != null){
pathSum(root.left, result, temp);
temp.remove(temp.size() - 1);
}
if(root.right != null){
pathSum(root.right, result, temp);
temp.remove(temp.size() - 1);
}
}
}
113、路徑總和 II
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
if(root == null){
return result;
}
find(root, result, temp, targetSum);
return result;
}
public void find(TreeNode root, List<List<Integer>> result, List<Integer> temp, int targetSum){
temp.add(root.val);
if(root.left == null && root.right == null){
int sum = 0;
for(int i = 0; i < temp.size(); i++){
sum += temp.get(i);
}
if(sum == targetSum){
result.add(new ArrayList<Integer>(temp));
}
}
if(root.left != null){
find(root.left, result, temp, targetSum);
temp.remove(temp.size() - 1);
}
if(root.right != null){
find(root.right, result, temp, targetSum);
temp.remove(temp.size() - 1);
}
}
}
106、從中序與後序遍歷序列構造二叉樹
class Solution {
public Map<Integer, Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return find(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
public TreeNode find(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend){
if(inbegin >= inend || pobegin >= poend){
return null;
}
int temp = map.get(postorder[poend - 1]);
int len = temp - inbegin;
TreeNode root = new TreeNode(inorder[temp]);
root.left = find(inorder, inbegin, temp, postorder, pobegin, pobegin + len);
root.right = find(inorder, temp + 1, inend, postorder, pobegin + len, poend - 1);
return root;
}
}
105、從前序與中序遍歷序列構造二叉樹
class Solution {
public Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i], i);
}
return find(inorder, 0, inorder.length, preorder, 0, preorder.length);
}
public TreeNode find(int[] inorder, int inbegin, int inend, int[] preorder, int prbegin, int prend){
if(inbegin >= inend || prbegin >= prend){
return null;
}
int temp = map.get(preorder[prbegin]);
int len = temp - inbegin;
TreeNode root = new TreeNode(inorder[temp]);
root.left = find(inorder, inbegin, temp, preorder, prbegin + 1, prbegin + len + 1);
root.right = find(inorder, temp + 1, inend, preorder, prbegin + len + 1, prend);
return root;
}
}
654、最大二叉樹
class Solution {
public Map<Integer, Integer> map;
public TreeNode constructMaximumBinaryTree(int[] nums) {
map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
map.put(nums[i], i);
}
return binaryTree(nums, 0, nums.length - 1);
}
public TreeNode binaryTree(int[] nums, int left, int right){
int max = -1;
for(int i = left; i <= right; i++){
max = max > nums[i] ? max : nums[i];
}
if(max == -1){
return null;
}else{
int index = map.get(max);
TreeNode root = new TreeNode(max);
root.left = binaryTree(nums, left, index - 1);
root.right = binaryTree(nums, index + 1, right);
return root;
}
}
}
617、合併二叉樹
/**
* 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 result = new TreeNode();
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 前序遍歷，遞歸
// if(root1 == null){
// return root2;
// }
// if(root2 == null){
// return root1;
// }
// root1.val += root2.val;
// root1.left = mergeTrees(root1.left,root2.left);
// root1.right = mergeTrees(root1.right,root2.right);
// return root1;
// 使用棧迭代
// if(root1 == null){
// return root2;
// }
// if(root2 == null){
// return root1;
// }
// Stack<TreeNode> stack = new Stack<>();
// stack.push(root1);
// stack.push(root2);
// while(!stack.isEmpty()){
// TreeNode cur2 = stack.pop();
// TreeNode cur1 = stack.pop();
// cur1.val += cur2.val;
// if(cur1.left != null && cur2.left != null){
// stack.push(cur1.left);
// stack.push(cur2.left);
// }else{
// if(cur1.left == null){
// cur1.left = cur2.left;
// }
// }
// if(cur1.right != null && cur2.right != null){
// stack.push(cur1.right);
// stack.push(cur2.right);
// }else{
// if(cur1.right == null){
// cur1.right = cur2.right;
// }
// }
// }
// return root1;
// 使用隊列迭代
if(root1 == null){
return root2;
}
if(root2 == null){
return root1;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root1);
queue.offer(root2);
while(!queue.isEmpty()){
TreeNode cur1 = queue.poll();
TreeNode cur2 = queue.poll();
cur1.val += cur2.val;
if(cur1.left != null && cur2.left != null){
queue.offer(cur1.left);
queue.offer(cur2.left);
}else{
if(cur1.left == null){
cur1.left = cur2.left;
}
}
if(cur1.right != null && cur2.right != null){
queue.offer(cur1.right);
queue.offer(cur2.right);
}else{
if(cur1.right == null){
cur1.right = cur2.right;
}
}
}
return root1;
}
}
700、二叉搜索樹中的搜索
/**
* 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 searchBST(TreeNode root, int val) {
// 遞歸
// if(root == null){
// return null;
// }
// TreeNode result = new TreeNode();
// if(root.val == val){
// result = root;
// }else if(root.val < val){
// result = searchBST(root.right,val);
// }else{
// result = searchBST(root.left,val);
// }
// return result;
// 迭代
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur.val == val){
return cur;
}else if(cur.val < val){
if(cur.right == null){
return null;
}
stack.push(cur.right);
}else{
if(cur.left == null){
return null;
}
stack.push(cur.left);
}
}
return null;
}
}
98、驗證二叉搜索樹
class Solution {
public boolean isValidBST(TreeNode root) {
// 需要從底層往上傳遞判斷結果，所以採用後序遍歷
if(root == null){
return true;
}
return isValidBST1(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean isValidBST1(TreeNode root,long left, long right){
if(root == null){
return true;
}
if(root != null && (root.val <= left || root.val >= right)){
return false;
}
boolean leftFlag = isValidBST1(root.left,left,root.val);
boolean rightFlag = isValidBST1(root.right,root.val,right);
if(leftFlag == false || rightFlag == false){
return false;
}
return leftFlag && rightFlag;
}
}
[530](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/)、二叉搜索樹的最小絕對差
class Solution {
public int result = Integer.MAX_VALUE;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
if(root == null){
return result;
}
traversal(root);
return result;
}
public void traversal(TreeNode cur){
if(cur == null){
return;
}
traversal(cur.left);
if(pre != null){
result = Math.min(result, cur.val - pre.val);
}
pre = cur;
traversal(cur.right);
}
}
[501](https://leetcode.cn/problems/find-mode-in-binary-search-tree/)、二叉搜索樹中的眾數
class Solution {
public int Maxcount;
public int count;
public List
public TreeNode pre;
public int[] findMode(TreeNode root) {
Maxcount = 0;
count = 0;
result = new ArrayList<>();
pre = null;
traversal(root);
int[] find = new int[result.size()];
for(int i = 0; i < result.size(); i++){
find[i] = result.get(i);
}
return find;
}
public void traversal(TreeNode root){
if(root == null){
return;
}
traversal(root.left);
if(pre == null || root.val != pre.val){
count = 1;
}else{
count++;
}
pre = root;
if(count > Maxcount){
result.clear();
result.add(root.val);
Maxcount = count;
}else if(count == Maxcount){
result.add(root.val);
}
traversal(root.right);
}
}
[236](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/)、二叉樹的最近公共祖先
class Solution {
public TreeNode result = null;
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// // 1、後序遍歷，從下往上傳遞，從遇到p或q開始，往上傳遞true,當某個節點也葉子節點都為true時，找到最近工祖先
// // 遞歸
// postOrder(root,p.val,q.val);
// return result;
// }
// public boolean postOrder(TreeNode root, int p, int q){
// if(root == null){
// return false;
// }
// boolean leftFlag = postOrder(root.left,p,q);
// boolean rightFlag = postOrder(root.right,p,q);
// if(leftFlag && rightFlag){
// result = root;
// return true;
// }
// if((root.val == q || root.val == p) && (leftFlag || rightFlag)){
// result = root;
// return true;
// }
// if(root.val == q || root.val == p){
// return true;
// }
// if(leftFlag || rightFlag){
// return true;
// }
// return false;
// }
}
[235](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/)、二叉搜索樹的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int left = Math.min(p.val,q.val);
int right = Math.max(p.val,q.val);
return infixTravesal(root,left,right);
}
public TreeNode infixTravesal(TreeNode root,int left,int right){
if(root == null){
return root;
}
if(root.val >= left && root.val <= right){
return root;
}
TreeNode tempLeft = infixTravesal(root.left,left,right);
TreeNode tempRight = infixTravesal(root.right,left,right);
if(tempLeft != null){
return tempLeft;
}else if(tempRight != null){
return tempRight;
}else{
return null;
}
}
}
[701](https://leetcode.cn/problems/insert-into-a-binary-search-tree/)、二叉搜索樹中的插入操作
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
TreeNode result = root;
travesal(root,val);
return result;
}
public void travesal(TreeNode root, int val){
if(root == null){
return;
}
if(root.val < val){
if(root.right == null){
root.right = new TreeNode(val);
return;
}else{
travesal(root.right,val);
}
}else{
if(root.val > val && root.left == null){
root.left = new TreeNode(val);
return;
}else{
travesal(root.left,val);
}
}
}
}
[450](https://leetcode.cn/problems/delete-node-in-a-bst/)、刪除二叉搜索樹中的節點
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
root = delete(root,key);
return root;
}
public TreeNode delete(TreeNode root,int key){
if(root == null){
return null;
}
if(root.val < key){
root.right = delete(root.right,key);
}else if(root.val > key){
root.left = delete(root.left,key);
}else{
if(root.left == null)
return root.right;
if(root.right == null)
return root.left;
TreeNode cur = root.right;
TreeNode temp = root.right;
while(temp.left != null){
temp = temp.left;
}
temp.left = root.left;
return cur;
}
return root;
}
}
[669](https://leetcode.cn/problems/trim-a-binary-search-tree/)、修剪二叉搜索樹
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);
}
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;
}
}
[108](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)、將有序數組轉換為二叉搜索樹
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return travesal(nums,0,nums.length - 1);
}
public TreeNode travesal(int[] nums, int left, int right){
if(left > right){
return null;
}
int mid = left + (right - left)/2;
TreeNode result = new TreeNode(nums[mid]);
result.left = travesal(nums,left,mid - 1);
result.right = travesal(nums,mid + 1, right);
return result;
}
}
[538](https://leetcode.cn/problems/convert-bst-to-greater-tree/)、把二叉搜索樹轉換為累加樹
class Solution {
public int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);
return root;
}
}
