2. 二叉树
java
class MyLinkedList {
private class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
private ListNode head;
private int size;
private ListNode tail;
// private ListNode dummyHead;
public MyLinkedList() {
head = new ListNode(0);
size = 0;
tail = new ListNode(0);
head.next = tail;
tail.next = null;
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
for (int i = 0; i <=index; i++) {
cur = cur.next;
if (cur == null) {
return -1;
}
}
return cur.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
// 新节点的下一个结点为head.next
newNode.next = head.next;
// head的next为newNode
head.next = newNode;
size++;
}
public void addAtTail(int val) {
tail.val=val;
tail.next = new ListNode(0);
tail = tail.next;
size++;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) {
return;
}
if (index == 0) {
addAtHead(val);
return;
}
if (index == size) {
addAtTail(val);
return;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next = newNode;
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
size--;
}
}3. 翻转链表
https://leetcode.cn/problems/reverse-linked-list/description/
java
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode current = head;
// a ->b -> c
// pre->current
while (current != null) {
// 记录b->c 之间的链接
ListNode tmp = current.next;
// b的链接指向前一个 a<-b c
current.next = pre;
// 前一个阶段开始后走 pre=b
pre = current;
// 当前的结点变成了current=c
current = tmp;
}
return pre;
}开始递归
java
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
return reverseList2(head, pre);
}
public ListNode reverseList2(ListNode current, ListNode pre) {
if (current == null) {
return pre;
}
//
ListNode tmp = current.next;
current.next = pre;
return reverseList2(tmp, current);
}4.两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
java
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
// 开始交换节点
ListNode first = cur.next;
ListNode second = cur.next.next;
first.next = second.next;
second.next = first;
cur.next = second;
cur = cur.next.next;
}
return dummy.next;
}5.删除节点的倒数第n个节点
使用快慢指针
java
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
// 快指针先走n步
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// 快慢指针同时走
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 此时slow就是倒数第n个节点的前一个节点
slow.next = slow.next.next;
return dummy.next;
}6.环形链表
这里需要做一下简单的数学证明
java
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode index1 = slow;
ListNode index2 = head;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}栈与队列
用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
java
class MyQueue {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
public MyQueue() {
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
// 将入栈元素全部加入到栈2中
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}用队列实现栈
java
class MyStack {
private Queue<Integer> queue1 = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
queue1.add(x);
}
public int pop() {
if (queue1.isEmpty()) {
return -1;
}
int size = queue1.size();
while (size > 1) {
queue1.add(queue1.poll());
size--;
}
return queue1.poll();
}
public int top() {
if (queue1.isEmpty()) {
return -1;
}
int size = queue1.size();
while (size > 1) {
queue1.add(queue1.poll());
size--;
}
int result = queue1.poll();
queue1.add(result);
return result;
}
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/有效的括号
https://leetcode.cn/problems/valid-parentheses/description/
java
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false;
}
// 栈顶元素如果不匹配
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}删除字符串中所有相邻重复项
1047
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
java
public String removeDuplicates(String s) {
char[] chars = s.toCharArray();
Stack<Character> stack = new Stack<>();
for (char c : chars) {
if (!stack.isEmpty() && stack.peek() == c) {
stack.pop();
} else {
stack.push(c);
}
}
return stack.stream().map(Object::toString).collect(Collectors.joining());
}逆波兰表达式
https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
https://blog.csdn.net/wenwenaier/article/details/121236053
java
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
// 如果遇到数字，则入栈
if (token.matches("[-+]?\\d+")) {
stack.push(Integer.parseInt(token));
} else {
// 如果遇到运算符，则从栈中弹出两个数字进行运算，并将结果入栈
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
}
}
}
return stack.pop();
}
}滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/description/
java
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> queue = new LinkedList();
int[] res = new int[nums.length - k + 1];
queue.add(nums[0]);
// 初始化栈
for (int i = 1; i < k; i++) {
int cur = nums[i];
// 如果栈不为空且当前元素小于栈顶元素，则将栈顶元素弹出。保持栈单调递减
while (!queue.isEmpty() && cur > queue.peekLast()) {
queue.pollLast();
}
queue.add(cur);
}
// System.out.println(queue.peek());
// System.out.println(nums[queue.peek()]);
res[0] = queue.peek();
for (int i = k; i < nums.length; i++) {
// 需要移除的数据为 窗口最左边的元素
if (!queue.isEmpty() && queue.peek() <= nums[i - k]) {
queue.poll();
}
// 栈不为空且当前元素小于栈顶元素，则将栈顶元素弹出。保持栈单调递减
int cur = nums[i];
while (!queue.isEmpty() && cur > queue.peekLast()) {
queue.pollLast();
}
queue.add(nums[i]);
res[i - k + 1] = queue.peek();
}
return res;
}
}前k个高频元素
求前k个高频元素，最适合大顶堆和小顶堆
java
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
// for(Map.Entry<Integer, Integer> entry : map.entrySet()){
// System.out.println(entry.getKey() + " " + entry.getValue());
// }
// 创建大顶堆. key 是数字， value 是数字出现的次数
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o1.getValue() - o2.getValue();
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
queue.offer(entry);
if (queue.size() > k) {
queue.poll();
}
}
// System.out.println("queue size: " + queue.size());
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--) {
// System.out.println(queue.peek().getKey() + " " + queue.peek().getValue());
res[i] = queue.poll().getKey();
}
return res;
}二叉树
二叉树的种类
理论基础
满二叉树
**一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1,则它就是满二叉树。
完全二叉树
除了底层
完全二叉树是这样定义的：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
上面的定义看起来比较复杂。事实上，完全二叉树的节点满足如下规律：
- 所有节点只存在3种情况：1、有左右2个孩子；2、只有左孩子；3、没有孩子（叶节点），即不存在只有右孩子的情况；
- 我们采用层序遍历的方式遍历节点，当遍历到某一个节点，它只有左孩子，或者没有孩子，则后序所有节点一定都是叶节点。
二叉搜索树
平衡二叉搜索树
左子树和右子树的高度差不能超过1
二叉树的存储方式
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表
c++
typedef struct BiNode
{
TElemType data; // 节点存储的数据
struct BiNode* lchild, * rchild; // 左右孩子指针
} BiNode, * BiTree;使用二叉链表存储二叉树可以有效解决空间浪费问题，因为每个节点只需要两个指针，分别指向左孩子和右孩子。然而，这种存储方式存在一个明显的局限：它无法直接进行回溯操作，即在遍历过程中，我们不知道每个节点的父节点是谁。
为了解决这一问题，我们可以使用三叉链表来存储二叉树。三叉链表在节点中引入了一个额外的指针，用于指向该节点的父节点。这样，每个节点包含三个指针：左孩子、右孩子和父节点，从而在遍历过程中，可以直接回溯到父节点，简化了操作，提升了效率。通过以下图示可以更直观地理解
依然是之前的二叉树，用三叉链表可以将子结点与父结点联系起来。如上图，B结点分别有两个指针指向子节点C和D，同时还有一个指针指向A。下面用代码表示：
java
typedef struct TriTNode
{
TelemType data; // 节点存储的数据
struct TriTNode* lchild, * parent, * rchild; // 三个指针：左孩子指针、父节点指针、右孩子指针
} TriTNode, * TriTree;线性存储
顺序存储指的是按照满二叉树的结点层次编号，依次存放二叉树中的数据元素。如下图所示
可以看到二叉树的顺序存储非常浪费空间，如左图，二叉树第五个结点虽然没有存储元素，但是这个结点依然要被占据。右图的单支树就是一种更加极端的情况。
二叉树的遍历
前序遍历，中序遍历，后序遍历
前序：中左右
中序：左中右
后序：左右中
递归遍历
java
package com.lkcoffee.demo;
import java.util.ArrayList;
import java.util.List;
/**
* 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 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 {
private List<Integer> result= new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
treeTraversal(root);
return result;
}
public void treeTraversal(TreeNode root) {
if (root == null) {
return;
}
// 前序：中 左 右
result.add(root.val);
treeTraversal(root.left);
treeTraversal(root.right);
}
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(1);
treeNode.right = new TreeNode(2);
treeNode.right.left = new TreeNode(3);
System.out.println(new Solution().preorderTraversal(treeNode));
}
}非递归遍历
使用栈来实现非递归遍历
前序
java
package com.lkcoffee.demo;
import java.util.ArrayList;
import java.util.List;
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 {
private List<Integer> result= new ArrayList<>();
private List<TreeNode> stack = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
stack.add(root);
while ( !stack.isEmpty()) {
TreeNode tmp= stack.remove(stack.size() - 1);
if(tmp == null){
continue;
}
result.add(tmp.val);
stack.add(tmp.right);
stack.add(tmp.left);
}
return result;
}
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(1);
treeNode.right = new TreeNode(2);
treeNode.right.left = new TreeNode(3);
System.out.println(new Solution().preorderTraversal(treeNode));
}
}前序：中左右
中序：左中右
后序：左右中
后序遍历
java
非递归遍历-中序遍历
中序：左中右
java
package com.lkcoffee.demo;
import java.util.ArrayList;
import java.util.List;
/**
* 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 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 {
private List<Integer> result = new ArrayList<>();
private List<TreeNode> stack = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
TreeNode tmp = root;
while ( tmp!=null || !stack.isEmpty()) {
if (tmp != null) {
stack.add(tmp);
tmp = tmp.left;
} else {
tmp = stack.remove(stack.size() - 1);
result.add(tmp.val);
tmp = tmp.right;
}
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode node1 = new TreeNode(2);
TreeNode node2 = new TreeNode(3);
root.right = node1;
node1.left = node2;
System.out.println(new Solution().inorderTraversal(root));
}
}二叉树的层序遍历
使用队列
http://ldleetcode.cn/problems/binary-tree-level-order-traversal/
java
package com.lkcoffee.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 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 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 {
private List<List<Integer>> result = new ArrayList<>();
private Queue<TreeNode> queue = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return result;
}
queue.add(root);
int level_size = 1;
int next_level_size = 0;
while (!queue.isEmpty()){
List<Integer> level_list = new ArrayList<>();
next_level_size=0;
for (int i = 0; i < level_size; i++) {
TreeNode node = queue.poll();
level_list.add(node.val);
if (node.left != null) {
queue.add(node.left);
next_level_size++;
}
if (node.right != null) {
queue.add(node.right);
next_level_size++;
}
}
level_size = next_level_size;
result.add(level_list);
}
return result;
}
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(3);
treeNode.left = new TreeNode(9);
treeNode.right = new TreeNode(20);
treeNode.right.left = new TreeNode(15);
treeNode.right.right = new TreeNode(7);
System.out.println(new Solution().levelOrder(treeNode));
}
}翻转二叉树
给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。
https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/description/
首先思考，使用哪种遍历方式最为方便？
前序：中左右。最为方便。逻辑也是这样子
java
public TreeNode flipTree(TreeNode root) {
if (root == null) {
return null;
}
// 前序遍历 中左右
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
flipTree(root.left);
flipTree(root.right);
return root;
}对称二叉树
首先需要判断下是哪种遍历顺序
只能后序遍历。左右中。需要收集孩子信息，只能是后序遍历
java
package com.lkcoffee.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 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 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 boolean isSymmetric(TreeNode root) {
return isSymmetric(root.left, root.right);
}
public boolean isSymmetric(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
return root1.val == root2.val && isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
}
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(2);
treeNode.left.left = new TreeNode(3);
treeNode.left.right = new TreeNode(4);
treeNode.right.left = new TreeNode(4);
treeNode.right.right = new TreeNode(3);
System.out.println(new Solution().isSymmetric(treeNode));
}
}二叉树的最大深度
二叉树的高度和深度有啥区别？
| 属性 | 定义 | 计算方式 |
|---|---|---|
| 深度 | 从根节点到该节点的边数 | 根节点深度为0 |
| 高度 | 从该节点到最远叶子节点的边数 | 叶子节点高度为0 |
- 深度是自上而下从根节点到当前节点的路径长度。
- 高度是自下而上从当前节点到最远叶子节点的路径长度。
- 树的高度等于根节点的高度，也等于树的最大深度。
要求深度-前序遍历，中左右。是自上而下
要求高度-是后序遍历，左右中，是从下而上
- 深度是自上而下从根节点到当前节点的路径长度。
- 高度是自下而上从当前节点到最远叶子节点的路径长度。
- 树的高度等于根节点的高度，也等于树的最大深度。
java
/**
* 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 int maxDepth(TreeNode root) {
return getMaxDepth(root,0);
}
public int getMaxDepth(TreeNode root,int depth){
if(root == null){
return depth;
}
return Math.max(getMaxDepth(root.left,depth+1),getMaxDepth(root.right,depth+1));
}
}二叉树的最小深度
https://leetcode.cn/problems/minimum-depth-of-binary-tree/
java
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return minDepth(root, 1);
}
public int minDepth(TreeNode root, int depth) {
// 才算叶子结点
if (root.left == null && root.right == null) {
return depth;
}
if (root.left == null) {
return minDepth(root.right, depth + 1);
}
if (root.right == null) {
return minDepth(root.left, depth + 1);
}
return Math.min(minDepth(root.left, depth + 1), minDepth(root.right, depth + 1));
}完全二叉树的节点个数
https://leetcode.cn/problems/count-complete-tree-nodes/description/
平衡二叉树
什么叫做：平衡二叉树也叫AVL树，它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
https://leetcode.cn/problems/balanced-binary-tree/
java
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
// 左右子树深度之差小于等于1 并且左右子树都是平衡的
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) {
return 0;
}
// 获取左右子树的深度
// 左右中-后序遍历
return Math.max(depth(root.left), depth(root.right)) + 1;
}如下有3棵树，分别判断下哪个是平衡二叉树？
图1：
图2：
图3：
图一，很明显就能看出图1中任何子树的高度差都在没有超过1，
图二，节点25的左子树高度是3，而右子树高度是5，高度差已经超过1；对于节点32而言，左子树高度是3，右子树高度是1，高度差已经超出1，所以该树不是平衡二叉树。
图三，对于节点25的左子树高度是3，而右子树高度是5，高度差已经超过1；对于节点28来说，左子树的高度是0，右指数的高度是2，高度差已经超过1；所以两处不平衡，不是平衡二叉树。
二叉树的所有路径
https://leetcode.cn/problems/binary-tree-paths/description/
java
private List<String> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private String pathToString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < path.size(); i++) {
sb.append(path.get(i));
if (i != path.size() - 1) {
sb.append("->");
}
}
return sb.toString();
}
public List<String> binaryTreePaths(TreeNode root) {
dfs(root);
return res;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
path.add(root.val);
if (root.left == null && root.right == null) {
res.add(pathToString());
}
dfs(root.left);
dfs(root.right);
path.remove(path.size() - 1);
}左叶子之和
给定二叉树的根节点 root ，返回所有左叶子之和。
java
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
if(root.left==null && root.right==null){
return 0;
}
// 左叶子节点收集数据
if (root.left != null && root.left.left == null && root.left.right == null) {
return root.left.val + sumOfLeftLeaves(root.right);
}
// 递归调用。左右中。后序遍历
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}二叉树-左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
https://leetcode.cn/problems/LwUNpT/description/
这个题目使用层序遍历，找到第一个元素，就非常的简单
java
private Queue<TreeNode> queue = new LinkedList<>();
private int res = 0;
public int findBottomLeftValue(TreeNode root) {
if(root == null){
return 0;
}
// 首先添加根节点
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(i == 0){
res = node.val;
}
// 添加左右节点
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return res;
}路径之和
java
private int sum = 0;
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return dfs(root, targetSum);
}
private boolean dfs(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
boolean result = false;
sum += root.val;
// 说明是叶子结点
if (root.left == null && root.right == null) {
if (sum == targetSum) {
return true;
}
}
if (root.left != null || root.right != null) {
result = dfs(root.left, targetSum) || dfs(root.right, targetSum);
}
sum -= root.val;
return result;
}从中序和后序遍历构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
中序- 左中右
后序- 左右中
java
/**
* 递归
*
* @param inorder 中序遍历
* @param postorder 后序遍历
* @return
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length == 0) {
return null;
}
// 初始化根结点
List<Integer> tmp = Arrays.stream(inorder).boxed().collect(Collectors.toList());
List<Integer> tmp1 = Arrays.stream(postorder).boxed().collect(Collectors.toList());
return getRoot(tmp, tmp1);
}
public TreeNode getRoot(List<Integer> qianxu, List<Integer> houxu) {
if (qianxu.size() == 0) {
return null;
}
TreeNode node = new TreeNode(houxu.get(houxu.size() - 1));
int root = houxu.get(houxu.size() - 1);
List<Integer> qianxu_left = new ArrayList<>();
List<Integer> qianxu_right = new ArrayList<>();
int i = qianxu.indexOf(root);
qianxu_left = qianxu.subList(0, i);
qianxu_right = qianxu.subList(i + 1, qianxu.size());
List<Integer> houxu_left = houxu.subList(0, qianxu_left.size());
List<Integer> houxu_right = houxu.subList(qianxu_left.size(), houxu.size() - 1);
node.left = getRoot(qianxu_left, houxu_left);
node.right = getRoot(qianxu_right, houxu_right);
return node;
}最大二叉树
https://leetcode.cn/problems/maximum-binary-tree/description/
java
private static int[] data;
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums == null) {
return null;
}
data = nums;
return buildTree(0, nums.length - 1);
}
public TreeNode buildTree(int start, int end) {
if (start > end) {
return null;
}
// 找到最大的index
int maxIndex = start;
for (int i = start + 1; i <= end; i++) {
if (data[i] > data[maxIndex]) {
maxIndex = i;
}
}
// 创建根节点
TreeNode root = new TreeNode(data[maxIndex]);
root.left = buildTree(start, maxIndex - 1);
root.right = buildTree(maxIndex + 1, end);
return root;
}合并二叉树
https://leetcode.cn/problems/merge-two-binary-trees/description/
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
java
/**
* 递归
* @param root1
* @param root2
* @return
*/
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) {
return root2;
}
if (root2 == null) {
return root1;
}
TreeNode node = new TreeNode(root1.val + root2.val);
node.left = mergeTrees(root1.left, root2.left);
node.right = mergeTrees(root1.right, root2.right);
return node;
}二叉搜索树
https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
java
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
if (root.val > val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}验证二叉搜索树
解题思路，二叉搜索树，中序遍历，就会变成一个递增的数组
java
// 表示中结点的值
public int max = 0;
public boolean addFirst = false;
public boolean isValid = true;
public boolean isValidBST(TreeNode root) {
bfs(root);
return isValid;
}
public void bfs(TreeNode root) {
if (root == null || !isValid) {
return;
}
bfs(root.left);
if (addFirst && root.val <= max) {
isValid = false;
}
max = root.val;
addFirst = true;
// 如果左边节点的值大于当前结点的值，则不是二叉搜索树
bfs(root.right);
}二叉搜索树的最小绝对差
https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/
java
private int min = Integer.MAX_VALUE;
private TreeNode pre = null;
public int getMinimumDifference(TreeNode root) {
if (root == null) {
return 0;
}
inOrder(root);
return min;
}
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
// 中序遍历
inOrder(root.left);
if (pre != null) {
min = Math.min(min, root.val - pre.val);
}
pre = root;
inOrder(root.right);
}二叉搜索树中的众数
https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
java
private List<Integer> result = new ArrayList<>();
private int count = 0;
private int maxCount = 0;
private TreeNode pre = null;
public int[] findMode(TreeNode root) {
dfs(root);
return result.stream().mapToInt(Integer::intValue).toArray();
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (pre == null || pre.val != root.val) {
count = 1;
pre = root;
} else {
// 如果当前节点的值和前一个节点的值相同，则计数加1
count++;
}
// 如果当前计数大于最大计数，则更新结果列表
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(root.val);
} else if (count == maxCount) {
if (result.get(result.size() - 1) != root.val) {
result.add(root.val);
}
}
dfs(root.right);
}二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 递归遍历
if (root == null) {
return root;
}
if (root.val == p.val || root.val == q.val) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}二叉搜索树的最近公共祖先
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/
java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
//当前结点值比p和q大，则去左子树找
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}二叉搜索树插入数据
java
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (root.val < val) {
root.right = insertIntoBST(root.right, val);
} else {
root.left = insertIntoBST(root.left, val);
}
return root;
}二叉搜索树删除结点
https://leetcode.cn/problems/delete-node-in-a-bst/
java
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
} else {
// 如果左右结点都为空，则返回null
if (root.left == null && root.right == null) {
return null;
}
// 如果左结点为空，则返回右子树
if (root.left != null && root.right == null) {
return root.left;
}
// 如果右结点为空，则返回左子树
if (root.left == null && root.right != null) {
return root.right;
}
// 如果左右结点都非空，则返回右子树的最小结点
TreeNode node = root.right;
while (node.left != null) {
node = node.left;
}
node.left = root.left;
return root.right;
}
return root;
}修建二叉树
java
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;
}将有序数组变成平衡二叉树
https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
java
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(null,nums,0,nums.length-1);
}
private TreeNode dfs(TreeNode root,int[] nums,int left,int right){
if(left>right){
return null;
}
int mid=(left+right)/2;
root=new TreeNode(nums[mid]);
root.left=dfs(root,nums,left,mid-1);
root.right=dfs(root,nums,mid+1,right);
return root;
}把二叉搜索树转换为累加树
https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
java
TreeNode pre = null;
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return null;
}
// 递归,变成右中左。倒叙去遍历。
convertBST(root.right);
if (pre != null) {
root.val += pre.val;
}
pre = root;
convertBST(root.left);
return root;
}使二叉树所有路径值相等的最小代价
https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/description/
java
找到最大三角形面积
https://leetcode.cn/problems/find-maximum-area-of-a-triangle/