数据结构
链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) return l1 == null ? l2 : l1;
if (l1.val > l2.val) {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
} else {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
ListNode head = new ListNode(0);
ListNode node = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
node.next = l1;
l1 = l1.next;
} else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
if (l1 != null) {
node.next = l1;
} else {
node.next = l2;
}
return head.next;
}Follow Up：合并两个有序链表并去重
public ListNode mergeSortedListWithoutDuplicates(ListNode node1, ListNode node2) {
//1.首先，根据两个结点情况判空，高效返回
if (node1 == null) return node2;
if (node2 == null) return node1;
//2. 新建一个结点，指向结点值较小的那个
ListNode head = (node1.val <= node2.val) ? node1 : node2;
//3. 创建两个指针，动态的指向 node1 和 node2
ListNode prev = head;
ListNode point = null;
while (node1 != null && node2 != null) {
if (node1.val <= node2.val) {
point = node1;
node1 = node1.next;
} else {
point = node2;
node2 = node2.next;
}
if (prev.val != point.val) {
prev.next = point;
prev = point;
}
}
//处理多余结点
while (node2 != null) {
if (prev.val != node2.val) {
prev.next = node2;
prev = node2;
}
node2 = node2.next;
}
while (node1 != null) {
if (prev.val != node1.val) {
prev.next = node1;
prev = node1;
}
node1 = node1.next;
}
// 将最后一个结点的下一个结点置位 null
prev.next = null;
return head;
}方法1:优先队列
将链表统一地送到优先队列，然后开始一个一个弹出队列的元素开始组装
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((l1,l2)->l1.val-l2.val);
for(ListNode l:lists){
if(l!=null) pq.offer(l);
}
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while(!pq.isEmpty()){
ListNode tmp = pq.poll();
curr.next = tmp;
curr = curr.next;
if(tmp.next!=null) pq.offer(tmp.next);
}
return dummy.next;
}方法2:堆排序
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
int len = lists.length;
return mergeKLists(lists, 0, len - 1);
}
private ListNode mergeKLists(ListNode[] lists, int l, int r) {
if (l == r) return lists[l];
int mid = l + (r - l) / 2;
ListNode l1 = mergeKLists(lists, l, mid);
ListNode l2 = mergeKLists(lists, mid + 1, r);
return mergeTwoSortedListNode(l1, l2);
}
private ListNode mergeTwoSortedListNode(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoSortedListNode(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoSortedListNode(l1, l2.next);
return l2;
}
} public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode second = prev.next.next;
ListNode nxt = second.next;
//step1
second.next = first;
//step2
first.next = nxt;
//step3
prev.next = second;
prev = first;
}
return dummy.next;
}方法1:迭代
需要注意是end节点的跳步的判断，可能不足k步，处理掉这种特殊情况
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, end = dummy;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) break;
ListNode start = prev.next;
ListNode nxt = end.next;
end.next = null;
prev.next = reverse(start);
start.next = nxt;
prev = start;
end = start;
}
return dummy.next;
}
/**
* 翻转链表，并返回翻转后的头结点
*
* @param head
* @return
*/
private ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}方法2:递归
public ListNode reverseKGroup(ListNode head, int k) {
ListNode tail = head;
for (int i = 0; i < k; i++) {
//当数量不足k的时候，返回head节点，不需要翻转了
if (tail == null) return head;
tail = tail.next;
}
//开始翻转[head,tail)范围内的链表，并返回翻转后的新的节点，也就是tail节点的上一个节点
ListNode new_head = reverse(head, tail);
//递归翻转以tail为头节点的如下部分链表
head.next = reverseKGroup(tail, k);
return new_head;//返回翻转后的新的头节点
}
//过程建figure.c
private ListNode reverse(ListNode head, ListNode tail) {
ListNode prev = null, cur = null;
while (head != tail) {
cur = head.next;//step1
head.next = prev;//step2
prev = head;//step3
head = cur;//step4
}
return prev;
}方法1:迭代
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode cur = head;
while (cur.next != null) {
//当前节点与下个节点的值如果相同，则跳下个节点
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}方法2:递归
出口条件
当
head节点和head.next节点为null的时候，开始返回head节点
逻辑
1.
head的next指针指向递归的结果2.
head的值和head.next的值是否相同，相同则返回head.next不同则返回head本身
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}方法3:双指针
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = head, nxt = head.next;
while (nxt != null) {
if (cur.val != nxt.val) {
cur = cur.next;
} else {
cur.next = nxt.next;
}
nxt = nxt.next;
}
return head;
}方法1:迭代
public ListNode deleteDuplicates(ListNode head) {
//哑结点
ListNode dummy = new ListNode(-1);
dummy.next = head;
//prev 和 cur节点
ListNode prev = dummy, cur;
while (prev.next != null) {//prev的next指针不为空
cur = prev.next;//每一轮的cur是prev的后一个
//当cur的后之后的cur相同跳过之后的
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
//需要判断链接状态，如果是相同的说明上一步没有重复的，不同的话，说明有重复的
if (prev.next != cur) {
prev.next = cur.next;
} else {
prev = prev.next;
}
}
return dummy.next;
}方法2:递归
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
if (head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
return head;
}
}方法1:双指针
public ListNode partition(ListNode head, int x) {
if (head == null) return head;
ListNode dummyBefore = new ListNode(0);
ListNode before = dummyBefore;
ListNode dummyAfter = new ListNode(0);
ListNode after = dummyAfter;
while (head != null) {
if (head.val < x) {
before.next = head;
before = before.next;
} else {
after.next = head;
after = after.next;
}
head = head.next;
}
before.next = dummyAfter.next;
after.next = null;
return dummyBefore.next;
}
只要是对的人，就算开始错过了，最终还是会再次相遇在一起的
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode lA = headA, lB = headB;
while (lA != lB) {
lA = (lA == null) ? headB : lA.next;
lB = (lB == null) ? headA : lB.next;
}
return lA;
}方法1.一遍遍历+哈希表
public Node copyRandomList(Node head) {
if (head == null) return null;
HashMap<Node, Node> map = new HashMap<>();
Node newHead = new Node(head.val);
map.put(head, newHead);
while (head != null) {
Node mirror = map.get(head);
if (head.next != null) {
map.putIfAbsent(head.next, new Node(head.next.val));
mirror.next = map.get(head.next);
}
if (head.random != null) {
map.putIfAbsent(head.random, new Node(head.random.val));
mirror.random = map.get(head.random);
}
head = head.next;
}
return newHead;
}方法2:两次遍历+哈希表
public Node copyRandomList(Node head) {
HashMap<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val, cur.next, cur.random));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}方法3:记忆化递归
1.从
head节点开始dfs遍历整个链表2.创建一个和当前节点
cur相同的节点mirror，并建立映射3.递归调用当前节点
cur的next节点和random节点，进行复制，让mirror节点的next和random指针分别指向这个复制的节点4返回复制的
mirror节点
Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) return null;
return dfs(head);
}
private Node dfs(Node cur) {
if (cur == null) return null;
if (map.containsKey(cur)) return map.get(cur);
//复制一个节点
Node mirror = new Node(cur.val);
//记忆化
map.put(cur, mirror);
//next 和 random 指针处理
mirror.next = dfs(cur.next);
mirror.random = dfs(cur.random);
return mirror;
}方法4:连接-恢复
2.遍历整个链表，处理
random指针3.定义一哑结点，然后让原来的
cur节点指向的mirror节点断开，恢复到原来的状态
public Node copyRandomList(Node head) {
Node cur = head;
while (cur != null) {
Node mirror = new Node(cur.val);
mirror.next = cur.next;
cur.next = mirror;
cur = cur.next.next;
}
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
Node dummy = new Node(-1);
Node p = dummy;
cur = head;
while (cur != null) {
Node mirror = cur.next;
p.next = mirror;
p = p.next;
cur.next = mirror.next;
cur = cur.next;
}
return dummy.next;
}方法1:快慢指针
public boolean hasCycle(ListNode head) {
if(head == null || head.next ==null) return false;
ListNode slow = head ,fast =head.next;
while(fast.next!=null && fast.next.next!=null){
//如果已经相等，说明已经相遇
if(slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}方法2:Hash
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.add(head)) return true;
head = head.next;
}
return false;
}d
方法1:双指针
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head.next;
//第一次相遇点
while (fast.next != null && fast.next.next != null) {
if (slow == fast) break;
slow = slow.next;
fast = fast.next.next;
}
if (slow != fast) return null;
//回到起始点
ListNode cur = head;
//第二次相遇
while (cur != slow.next) {
cur = cur.next;
slow = slow.next;
}
return cur;
}方法1:快慢指针+翻转
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = head, fast = head;
//快慢指针找整个链表的中点，准备切分
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
//翻转第二段链表，并返回第二段链表的第一个节点
ListNode second = reverse(tmp);
//前一段链表的第一个节点
ListNode first = dummy.next;
//串联两段链表
while (second != null) {
ListNode l2 = second.next;
second.next = first.next;
first.next = second;
first = second.next;
second = l2;
}
}
//翻转链表
private ListNode reverse(ListNode head) {
ListNode cur = head, pre = null, next;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}方法2:头插法
public void reorderList(ListNode head) {
ListNode cur = head;
int cnt = 0;//链表的数量
while (cur != null) {
cnt++;
cur = cur.next;
}
//头插的次数，偶数个的话-1
int times = (cnt % 2 == 1) ? cnt / 2 : cnt / 2 - 1;
cur = head;//重置cur节点
for (int i = 0; i < times; i++) {
ListNode t = head;//找到要移动的节点前面的那个节点
for (int j = 2; j < cnt; j++) {
t = t.next;
}
//头插
t.next.next = cur.next;
cur.next = t.next;
t.next = null;
if (cur.next != null) cur = cur.next.next;
}
}方法1：快排
//quick sort
public ListNode sortList(ListNode head) {
return quickSort(head, null);
}
public ListNode partition(ListNode first, ListNode end) {
if (first == end) return first;
ListNode head = first, tmp = null, prev = head;
int pivot = head.val;
while (prev != end) {
tmp = prev.next;
if (tmp == end) break;
if (tmp != null && tmp.val < pivot) {
prev.next = tmp.next;
tmp.next = head;
head = tmp;
} else {
prev = tmp;
}
}
return head;
}
public ListNode quickSort(ListNode start, ListNode end) {
if (start == end) return start;
ListNode partition = partition(start, end);
ListNode p1 = quickSort(partition, start);
ListNode p2 = quickSort(start.next, end);
start.next = p2;
return p1;
}方法2:归并排序
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
//快慢指针找分隔点，slow为下一段的起点，prev是slow的前一个节点
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
//切断
prev.next = null;
//分治（递归）
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
//合并
return merge(l1, l2);
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) p.next = l1;
if (l2 != null) p.next = l2;
return dummy.next;
}public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}方法1:递归
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newNode = reverseList(head.next);
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的next是5，next.next是空
//所以head.next.next 就是5->4
head.next.next = head;
//head的next需要断开
head.next = null;
return newNode;
}方法2:迭代
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while(cur!=null){
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}方法1:头插法
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) return null;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
for (int i = 0; i < m - 1; i++) {
prev = prev.next;
}
ListNode start = prev.next, then = start.next;
for (int i = 0; i < n - m; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
}方法2:迭代
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = pre.next;
for (int i = 1; i < m; i++) {
pre = pre.next;
cur = cur.next;
}
for (int i = 0; i < n - m; i++) {
ListNode tmp = cur.next;
cur.next = tmp.next;
tmp.next = pre.next;
pre.next = tmp;
}
return dummy.next;
}树
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
方法1:DFS
public int numTrees(int n) {
return dfs(n);
}
private int dfs(int n) {
if (n == 0 || n == 1) return 1;
int cnt = 0;
for (int i = 0; i <= n - 1; i++) {
cnt += dfs(i) * dfs(n - 1 - i);
}
return cnt;
}方法2:DP
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
TreeNode prev = null;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) {
return false;
}
if (prev != null && prev.val >= root.val) return false;
prev = root;
if (!isValidBST(root.right)) {
return false;
}
return true;
}public boolean isSymmetric(TreeNode root) {
if (root == null) return false;
return helper(root.left, root.right);
}
public boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return left.val == right.val && helper(left.left, right.right) && helper(left.right, right.left);
}方法1:BFS
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> sub = new ArrayList<>();
for (int i = 0; i < size; ++i) {
TreeNode curr = q.poll();
sub.add(curr.val);
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
res.add(new ArrayList<>(sub));
}
return res;
}方法1:DFS
public int maxDepth(TreeNode root) {
return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}方法2:BFS
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
if (curr.left != null) queue.offer(curr.left);
if (curr.right != null) queue.offer(curr.right);
}
level++;
}
return level;
}//二叉树问题 通过先序和中序数组生成后序数组...
public static int[] getPosArray(int[] pre, int[] in) {
if (pre == null || in == null) {
return null;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
map.put(in[i], i);
}
int[] pos = new int[in.length];
preAndIn(pre, 0, pre.length - 1, in, 0, in.length - 1, pos, pos.length - 1, map);
return pos;
}
/**
* @param pre 前序数组
* @param preStart 前序数组的开始节点下标
* @param preEnd 前序节点的结束节点下标
* @param in 中序数组
* @param inStart 中序数组的开始节点下标
* @param inEnd 中序节点的结束节点下标
* @param pos
* @param posEnd
* @param map
* @return
*/
public static int preAndIn(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd, int[] pos, int posEnd, Map<Integer, Integer> map) {
if (preStart > preEnd) {
return posEnd;
}
//每一步按root节点进行切分
int value = pre[preStart];
pos[posEnd--] = value;
int index = map.get(value);
posEnd = preAndIn(pre, preStart + index - inStart + 1, preEnd, in, index + 1, inEnd, pos, posEnd, map);
posEnd = preAndIn(pre, preStart + 1, preStart + index - inStart, in, inStart, index - 1, pos, posEnd, map);
return posEnd;
}Map<Integer, Integer> rootMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
for (int i = 0; i < inorder.length; i++) rootMap.put(inorder[i], i);
return buildTreeDFS(preorder, 0, preorder.length - 1
, inorder, 0, inorder.length);
}
public TreeNode buildTreeDFS(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]);
int mid = rootMap.get(preorder[preStart]);
if (mid < 0) return null;
root.left = buildTreeDFS(preorder, preStart + 1, preStart + (mid - inStart)
, inorder, inStart, mid - 1);
root.right = buildTreeDFS(preorder, preStart + (mid - inStart) + 1, preEnd
, inorder, mid + 1, inEnd);
return root;
} public int minDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int res = Integer.MAX_VALUE;
if (root.left != null) res = Math.min(res, minDepth(root.left));
if (root.right != null) res = Math.min(res, minDepth(root.right));
return res + 1;
}follow up
如何求倒数第2个或者倒数第k个最小深度？
//k:叶子节点， v:叶子节点的最小深度
Map<TreeNode, Integer> map = new HashMap<>();
public int getBottomKMinDepth(TreeNode root, int k) {
//遍历获取map
helper(root, 0);
List<Integer> list = new ArrayList<>(map.values());
int res = getBottomK(list, k);
return res;
}
private int getBottomK(List<Integer> list, int k) {
//大根堆，从栈顶到栈底 依次从大到小
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int x : list) {
if (!pq.isEmpty() && pq.size() >= k && pq.peek() > x) pq.poll();
if (pq.isEmpty() || pq.size() < k) pq.offer(x);
}
return pq.isEmpty() ? -1 : pq.peek();
}
private int helper(TreeNode root, int depth) {
if (root == null) return 0;
if (root.left == null && root.right == null) {
map.put(root, depth + 1);
return 1;
}
int res = Integer.MAX_VALUE;
if (root.left != null) res = Math.min(res, helper(root.left, depth + 1));
if (root.right != null) res = Math.min(res, helper(root.right, depth + 1));
return res + 1;
}方法1:迭代
1.定义一个
cur节点，将其入栈2.对
cur节点的左子树重复步骤1，直到左子树为空3.弹出栈内保存到左子树的节点，开始遍历右子树，重复步骤1
4.遍历完整个二叉树，结束
List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stk = new Stack<>();
TreeNode cur = root;
while (cur != null || !stk.isEmpty()) {
if (cur != null) {
res.add(cur.val);
stk.push(cur);
cur = cur.left;
} else {
TreeNode tmp = stk.pop();
cur = tmp.right;
}
}
return res;
}方法1:迭代
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
TreeNode cur = root;
while (cur != null || !stk.isEmpty()) {
if (cur != null) {
stk.push(cur);
cur = cur.left;
} else {
cur = stk.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}方法2:递归
List<Integer> inoderList = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) return inoderList;
inorderTraversal(root.left);
inoderList.add(root.val);
inorderTraversal(root.right);
return inoderList;
}方法3:Morris遍历
public void inOrderByMorris(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {//步骤1
System.out.print(curr.val + " ");
curr = curr.right;
} else {//步骤2
TreeNode predecessor = getPredecessor(curr);
if (predecessor.right == null) {//步骤2.a
predecessor.right = curr;
curr = curr.left;
} else if (predecessor.right == curr) {//步驟2.b
predecessor.right = null;
System.out.print(curr + " ");
curr = curr.right;
}
}
}
}
private TreeNode getPredecessor(TreeNode curr) {
TreeNode predecessor = curr;
if (curr.left != null) {
predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
}
return predecessor;
}方法1:DFS
TreeNode prev = null;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (prev != null && prev.val >= root.val) return false;
prev = root;
if (!isValidBST(root.right)) return false;
return true;
}方法2:BFS
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode prev = null;
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
if (prev != null && prev.val >= root.val) return false;
prev = root;
root = root.right;
}
return true;
}方法1：DFS
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}方法2：BFS
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
Queue<TreeNode> queue1 = new LinkedList<>();
Queue<TreeNode> queue2 = new LinkedList<>();
queue1.offer(p);
queue2.offer(q);
while (!queue1.isEmpty()) {
TreeNode currP = queue1.poll();
TreeNode currQ = queue2.poll();
if (currP == null && currQ == null) continue;
if (currP.val != currQ.val) return false;
TreeNode currPLeft = currP.left;
TreeNode currPRight = currP.right;
TreeNode currQLeft = currQ.left;
TreeNode currQRight = currQ.right;
if (currPLeft == null ^ currQLeft == null) return false;
if (currPRight == null ^ currQRight == null) return false;
if (currPLeft != null) queue1.offer(currPLeft);
if (currPRight != null) queue1.offer(currPRight);
if (currQLeft != null) queue2.offer(currQLeft);
if (currQRight != null) queue2.offer(currQRight);
}
return true;
} public boolean isSymmetric(TreeNode root) {
if (root == null) return false;
return helper(root.left, root.right);
}
public boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return left.val == right.val && helper(left.left, right.right) && helper(left.right, right.left);
}public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
List<Integer> levelList = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (level % 2 == 0) levelList.add(cur.val);
else levelList.add(0, cur.val);
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
level++;
result.add(levelList);
}
return result;
}方法1：递归
public boolean isBalanced(TreeNode root) {
if (root != null) {
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) return false;
if (!isBalanced(root.left)) return false;
return isBalanced(root.right);
}
return true;
}
private int getHeight(TreeNode root) {
return root == null ? 0 : Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}方法2：迭代
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
TreeNode cur = stack.pop();
int lh = getHeight(cur.left);
int rh = getHeight(cur.right);
if (Math.abs(lh - rh) > 1) return false;
root = cur.right;
}
}
return true;
}
public int getHeight(TreeNode node) {
int res = 0;
if (node == null) return res;
Queue<TreeNode> que = new LinkedList<>();
que.offer(node);
while (!que.isEmpty()) {
int size = que.size();
res++;
while (size-- > 0) {
TreeNode cur = que.poll();
if (cur.left != null) que.offer(cur.left);
if (cur.right != null) que.offer(cur.right);
}
}
return res;
}int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
public int dfs(TreeNode root) {
if (root == null) return 0;
int lval = Math.max(dfs(root.left), 0);
int rval = Math.max(dfs(root.right), 0);
res = Math.max(res, root.val + lval + rval);
return root.val + Math.max(lval, rval);
}Follow up :如何打印出路径
相同的值的路径，全部打印出来
│ ┌── 7
│ ┌── 20
│ │ └── 15
└── -100
│ ┌── 17
└── 9
└── 16
[[16,9,17],[15,20,7]] int maxPath = Integer.MIN_VALUE;
List<List<Integer>> resPath = new ArrayList<>();
public int maxPathSum(TreeNode root) {
dfs(root);
System.out.println(JSON.toJSONString(resPath));
return maxPath;
}
private Pair dfs(TreeNode root) {
if (root == null) return new Pair(0, new ArrayList<>());
Pair lp = dfs(root.left);
Pair rp = dfs(root.right);
int res = root.val;
List<Integer> subPath = new ArrayList<>();
if (lp.sum > 0 && lp.sum > rp.sum) {
res += lp.sum;
subPath.addAll(lp.path);
subPath.add(root.val);
} else if (rp.sum > 0 && rp.sum > lp.sum) {
res += rp.sum;
subPath.addAll(rp.path);
subPath.add(root.val);
} else {
subPath.add(root.val);
}
if (res >= maxPath) {
if (res > maxPath) resPath.clear();
maxPath = res;
resPath.add(new ArrayList<>(subPath));
}
if (lp.sum + rp.sum + root.val >= maxPath) {
List<Integer> t = new ArrayList<>();
t.addAll(lp.path);
t.add(root.val);
t.addAll(rp.path);
if (lp.sum + rp.sum + root.val > maxPath) resPath.clear();
maxPath = lp.sum + rp.sum + root.val;
resPath.add(new ArrayList<>(t));
}
return new Pair(res, subPath);
}
static class Pair {
int sum = 0;
List<Integer> path;
public Pair(int sum, List<Integer> path) {
this.sum = sum;
this.path = path;
}
}方法1:迭代法
前序遍历和后序遍历之间的关系：
前序遍历顺序为：根 -> 左 -> 右
后序遍历顺序为：左 -> 右 -> 根
如果1： 我们将前序遍历中节点插入结果链表尾部的逻辑，修改为将节点插入结果链表的头部
那么结果链表就变为了：右 -> 左 -> 根
如果2： 我们将遍历的顺序由从左到右修改为从右到左，配合如果1
那么结果链表就变为了：左 -> 右 -> 根
这刚好是后序遍历的顺序
基于这两个思路，我们想一下如何处理：
修改前序遍历代码中，节点写入结果链表的代码，将插入队尾修改为插入队首
修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑，变为先查看右节点再查看左节点
链接来自：这里
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
TreeNode cur = root;
while (cur != null || !stk.isEmpty()) {
if (cur != null) {
res.add(0, cur.val);
stk.push(cur);
cur = cur.right;
} else {
TreeNode tmp = stk.pop();
cur = tmp.left;
}
}
return res;
}class BSTIterator {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = null;
public BSTIterator(TreeNode root) {
cur = root;
}
/**
* @return the next smallest number
*/
public int next() {
int res = -1;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res = cur.val;
cur = cur.right;
break;
}
return res;
}
/**
* @return whether we have a next smallest number
*/
public boolean hasNext() {
return (cur != null || !stack.isEmpty());
}
}方法1:DFS
public TreeNode invertTree(TreeNode root) {
if(root ==null) return null;
TreeNode l = invertTree(root.left);
TreeNode r = invertTree(root.right);
root.left = r;
root.right = l;
return root;
}最近公共祖先(LCA|Lowest Common Ancestor)
一棵有根的树T。两个节点n1和n2之间的最低共同祖先被定义为T中具有n1和n2作为后代的最低节点（允许一个节点是其自身的后代）。 T中n1和n2的LCA是距离根最远的n1和n2的共同祖先。例如，作为确定树中节点对之间距离的过程的一部分，计算最低共同祖先可能是有用的：从n1到n2的距离可以计算为从根到n1的距离，加上从根到n2的距离，减去从根到其最低共同祖先的距离的两倍。
方法1：DFS
思路：
1.left和right都为空，说明root的左右子树中都不包含p和q节点，返回null即可
2.left不为空，right为空，说明p和q不在右子树中（因为右子树为空了），这时，返回left，这里面有下面的两种情况：
p和q都在left即左子树上，而root节点恰好指向了p或者qp和q都在left即左子树上，而root节点未指向了p或者q，指向的是最近公共祖先节点
3.right不为空，left为空，说明p和q不在左子树中（因为左子树为空了），这时，返回right，这里面有下面的两种情况：
p和q都在right即右子树上，而root节点恰好指向了p或者qp和q都在right即右子树上，而root节点未指向了p或者q，指向的是最近公共祖先节点
4.left不为空，并且right不为空，说明p和q分布在root节点的左右子树的两侧，这时root为p和q的最近公共祖先节点，返回
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 root;
if(left !=null) return left;
if(right!=null) return right;
return null;
}测试
public static void main(String[] args) {
_3rd handler = new _3rd();
TreeNode root = TreeNodeIOUtils.transform("[3,5,1,6,2,0,8,null,null,7,4]");
TreeNode p = root.left;//5
TreeNode q = root.right;//1
// TreeNode ancestor = handler.lowestCommonAncestor(root, p, q);
// System.out.printf("%d\n", ancestor.val);
root = TreeNodeIOUtils.transform("[3,5,1,6,null,null,null,7,2,null,null,null,4]");
p = root.left.left.left;
q = root.left.left.right.right;
TreeNode ancestor = handler.lowestCommonAncestor(root, p, q);
System.out.printf("%d\n", ancestor.val);
}方法2：迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//存当前节点的父节点，k:当前节点，v:当前节点的父节点，root节点的父节点为null
Map<TreeNode, TreeNode> parent = new HashMap<>();
parent.put(root, null);
Deque<TreeNode> stk = new ArrayDeque<>();
stk.push(root);
//step1:率先找到p或者q，先左节点，后右节点，然后出栈的时候，选右节点优先
while (!parent.containsKey(p) || !parent.containsKey(q)) {
TreeNode cur = stk.pop();
if (cur.left != null) {
parent.put(cur.left, cur);
stk.push(cur.left);
}
if (cur.right != null) {
parent.put(cur.right, cur);
stk.push(cur.right);
}
}
//step2：set收集的是p节点的所有祖先节点，包括p节点的直系父节点
Set<TreeNode> set = new HashSet<>();
while (p != null) {
set.add(p);
p = parent.get(p);
}
//step3:找q的父节点，第一个出现在set集合中的即是LCA
while (!set.contains(q)) {
q = parent.get(q);
}
return q;
}如果这棵二叉树是一棵二叉搜索树(BST)呢？
对于BST，当从上到下遍历树时，位于两个数字n1和n2之间的第一个节点是LCA，即位于n1和n2（n1<=n<=n2）之间的具有最低深度的第一个节点n。所以只要递归地遍历BST，如果节点的值大于n1和n2，那么LCA位于节点的左侧，如果它小于n1和n2，那么LCA位于右侧。否则，根为LCA（假设BST中同时存在n1和n2)
方法1：DFS
思路：
1.创建一个递归函数，该函数接受一个节点和两个值n1和n2。
2.如果当前节点的值小于n1和n2，则LCA位于右侧子树中。调用右子树的递归函数。
3.如果当前节点的值大于n1和n2，则LCA位于左子树中。调用左子树的递归函数。
4.如果上述两种情况均为false，则将当前节点作为LCA返回
static class _2nd_3 {
public static void main(String[] args) {
_2nd_3 handler = new _2nd_3();
TreeNode root = TreeNodeIOUtils.transform("[20,8,22,4,12,null,null,null,null,10,14]");
int n1 = 10, n2 = 14;
TreeNode res1 = handler.lca(root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + res1.val);
n1 = 14;
n2 = 8;
res1 = handler.lca(root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + res1.val);
n1 = 10;
n2 = 22;
res1 = handler.lca(root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + res1.val);
}
public TreeNode lca(TreeNode root, int n1, int n2) {
if (root == null) return null;
if (root.val > n1 && root.val > n2) return lca(root.left, n1, n2);
if (root.val < n1 && root.val < n2) return lca(root.right, n1, n2);
return root;
}
}
//output
│ ┌── 22
└── 20
│ ┌── 14
│ ┌── 12
│ │ └── 10
└── 8
└── 4
LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20复杂度分析：
时间复杂度：O(h)，h为树的高度
空间复杂度：O(h)，如果忽略递归堆栈空间，则上述解决方案的空间复杂度是常数级别。
迭代实现：上述解决方案使用递归。递归解决方案需要函数调用堆栈形式的额外空间。因此，可以实现一个迭代解决方案，它不会以函数调用堆栈的形式占用空间。
public TreeNode lca_iterate(TreeNode root, int n1, int n2) {
while (root != null) {
if (root.val > n1 && root.val > n2) root = root.left;
else if (root.val < n1 && root.val < n2) root = root.right;
else break;
}
return root;
}复杂度分析：
时间复杂度：O(h)，h为树的高度
空间复杂度：O(1)，间复杂度是常数级别。
Reference
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "[]";
StringBuilder sb = new StringBuilder("[");
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (cur != null) {
sb.append(cur.val).append(",");
q.offer(cur.left);
q.offer(cur.right);
} else {
sb.append("null").append(",");
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("[]")) return null;
String[] arr = data.substring(1, data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int idx = 1;
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (!arr[idx].equals("null")) {
cur.left = new TreeNode(Integer.parseInt(arr[idx]));
q.offer(cur.left);
}
idx++;
if (!arr[idx].equals("null")) {
cur.right = new TreeNode(Integer.parseInt(arr[idx]));
q.offer(cur.right);
}
idx++;
}
return root;
}
} public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "[]";
StringBuilder sb = new StringBuilder("[");
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (cur != null) {
sb.append(cur.val).append(",");
q.offer(cur.left);
q.offer(cur.right);
} else {
sb.append("null").append(",");
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("[]")) return null;
String[] arr = data.substring(1, data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int idx = 1;
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (!arr[idx].equals("null")) {
cur.left = new TreeNode(Integer.parseInt(arr[idx]));
q.offer(cur.left);
}
idx++;
if (!arr[idx].equals("null")) {
cur.right = new TreeNode(Integer.parseInt(arr[idx]));
q.offer(cur.right);
}
idx++;
}
return root;
}
}方法2:找分割点
public static class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
dfs1(root, sb);
return sb.toString();
}
private void dfs1(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
sb.append(root.val).append(" ");
dfs1(root.left, sb);
dfs1(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() == 0) return null;
String[] arr = data.split(" ");
List<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
list.add(Integer.parseInt(arr[i]));
}
TreeNode root = dfs2(list, 0, list.size() - 1);
return root;
}
private TreeNode dfs2(List<Integer> list, int l, int r) {
if (l > r) return null;
TreeNode root = new TreeNode(list.get(l));
int k = l + 1;
while (k <= r && list.get(k) < list.get(l)) k++;
root.left = dfs2(list, l + 1, k - 1);
root.right = dfs2(list, k, r);
return root;
}
}/**
* https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/
*/
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key > root.val) root.right = deleteNode(root.right, key);
if (key < root.val) root.left = deleteNode(root.left, key);
if (key == root.val) {
if (root.left == null && root.right == null) root = null;
else if (root.right != null) {
root.val = successor(root);
root.right = deleteNode(root.right, root.val);
} else if (root.right == null) {
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val);
}
}
return root;
}
public int successor(TreeNode root) {
root = root.right;
while (root.left != null) root = root.left;
return root.val;
}
public int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) root = root.right;
return root.val;
}方法1:BFS
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "[]";
StringBuilder sb = new StringBuilder("[");
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (cur != null) {
sb.append(cur.val).append(",");
q.offer(cur.left);
q.offer(cur.right);
} else {
sb.append("null").append(",");
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("[]")) return null;
String[] arr = data.substring(1, data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int idx = 1;
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (!arr[idx].equals("null")) {
cur.left = new TreeNode(Integer.parseInt(arr[idx]));
q.offer(cur.left);
}
idx++;
if (!arr[idx].equals("null")) {
cur.right = new TreeNode(Integer.parseInt(arr[idx]));
q.offer(cur.right);
}
idx++;
}
return root;
}方法2:DFS
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "null";
return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
return dfs(queue);
}
private TreeNode dfs(Queue<String> queue) {
String v = queue.poll();
if ("null".equals(v)) return null;
TreeNode node = new TreeNode(Integer.parseInt(v));
node.left = dfs(queue);
node.right = dfs(queue);
return node;
}
}方法1:BFS
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> sub = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node cur = q.poll();
sub.add(cur.val);
for (Node child : cur.children) {
q.offer(child);
}
}
res.add(new ArrayList<>(sub));
}
return res;
}方法2:DFS
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
dfs(root, 0);
return res;
}
/**
* @param root 当前处理到的节点
* @param level 层数
*/
private void dfs(Node root, int level) {
if (root == null) return;
if (level == res.size()) res.add(new ArrayList<>());
res.get(level).add(root.val);
for (Node child : root.children) dfs(child, level + 1);
}Follow Up：1.自底向上的层序遍历如何做？
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> sub = new ArrayList<>();
for (int i = 0; i < size; ++i) {
Node curr = q.poll();
sub.add(curr.val);
if (curr.children != null && curr.children.size() != 0) {
for (int j = 0; j < curr.children.size(); j++) {
q.offer(curr.children.get(j));
}
}
}
//倒序插入
res.add(0, new ArrayList<>(sub));
}
return res;
}Follow Up：2.按奇偶层数锯齿层序遍历如何做？
方法1：递归+分情况讨论
当前节点的值比目标值小，说明目标节点在右子树上，删除后的结果挂在当前节点的右孩子上
当前节点的值比目标值大，说明目标节点在左子树上，删除后的结果挂在当前节点的左孩子上
如果当前节点与目标值相同，说明当前节点为目标节点，要删除当前节点，分为以下三种情况：
其无左子树：其右子树顶替其位置，删除了该节点
其无右子树：其左子树顶替其位置，删除了该节点
其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;//节点为空，返回
//根据二叉树的性质分 < > =
if (root.val < key) root.right = deleteNode(root.right, key);
else if (root.val > key) root.left = deleteNode(root.left, key);
else {
//当前节点的左子树为空，返回当前的右子树
if (root.left == null) return root.right;
//当前节点的右子树为空，返回当前的左子树
if (root.right == null) return root.left;
//左右子树都不为空，找到右孩子的最左节点 记为p
TreeNode node = root.right;
while (node.left != null) {
node = node.left;
}
//将当前节点在左子树挂在p的孩子上
node.left = root.left;
//当前节点的右子树替换掉当前节点，完成当前节点的删除
root = root.right;
}
return root;
}方法1：DFS
public int[] findFrequentTreeSum(TreeNode root) {
if (root == null) return new int[]{};
dfs(root);
List<Integer> list = new ArrayList<>();
for (int k : map.keySet()) {
if (map.get(k) == maxx) list.add(k);
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
return res;
}
int maxx = 0;//出现的最大的次数
//记录当前出现的sum 的次数
Map<Integer, Integer> map = new HashMap<>();
private int dfs(TreeNode root) {
if (root == null) return 0;
int l = dfs(root.left);
int r = dfs(root.right);
int s = l + root.val + r;
map.put(s, map.getOrDefault(s, 0) + 1);
maxx = Math.max(maxx, map.get(s));
return s;
}方法1：BFS
层序遍历，迭代每一层，取最左边的
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
TreeNode res = root;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
if (i == 0) res = q.peek();
TreeNode cur = q.poll();
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
}
return res.val;
}方法2：DFS
先左子树节点后右子树节点，左子树切换到右子树的时机进行最大深度
maxDepth的更新与记录，并保存结果值
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
return res;
}
int maxDepth = -1, res = 0;
private void dfs(TreeNode root, int depth) {
if (root == null) return;
dfs(root.left, depth + 1);
if (depth > maxDepth) {
maxDepth = depth;
res = root.val;
}
dfs(root.right, depth + 1);
}Follow Up:找树右下角的值
方法1：BFS
记录每一层的最后一个值
public int findBottomRightValue(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
TreeNode res = root;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
if (i == size - 1) res = q.peek();
TreeNode cur = q.poll();
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
}
return res.val;
}方法2：DFS
先右子树后左子树
public int findBottomRightValue(TreeNode root) {
dfs(root, 0);
return res;
}
int maxDepth = -1, res = 0;
private void dfs(TreeNode root, int depth) {
if (root == null) return;
dfs(root.right, depth + 1);
if (depth > maxDepth) {
maxDepth = depth;
// System.out.printf("%d->",root.val);
res = root.val;
}
dfs(root.left, depth + 1);
}方法1：层序遍历
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
if (root != null) q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
int t = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
t = Math.max(t, cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
res.add(t);
}
return res;
}方法2：DFS
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
dfs(root, 0, res);
return res;
}
//depth表当前处理的节点的深度
private void dfs(TreeNode root, int depth, List<Integer> res) {
if (depth == res.size()) {//第一次来到该深度的节点
res.add(root.val);
} else {//非第一次来到该层
res.set(depth, Math.max(root.val, res.get(depth)));
}
if (root.left != null) dfs(root.left, depth + 1, res);
if (root.right != null) dfs(root.right, depth + 1, res);
}方法1:DFS
int res = 1;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return res - 1;
}
public int dfs(TreeNode root) {
if (root == null) return 0;//如果达到叶子节点的子节点，返回0
int leftDepth = dfs(root.left);//遍历左子树
int rightDepth = dfs(root.right);//遍历右子树
res = Math.max(res, leftDepth + rightDepth + 1);//计算最大直径
return Math.max(leftDepth, rightDepth) + 1;//返回最大的深度
}方法1：dfs
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null || subRoot == null) {
return root == null && subRoot == null;
}
//注意，如果比较的是root，则比较相同的树:isSameTree
//如果比较的是root左右子节点，则比较的是不是子树 ：isSubtree
return isSameTree(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode source, TreeNode target) {
if (source == null || target == null) {
return source == null && target == null;
}
return source.val == target.val &&
isSameTree(source.left, target.left) &&
isSameTree(source.right, target.right);
} List<Integer> res = new ArrayList<>();
public List<Integer> preorder(Node root) {
helper(root);
return res;
}
private void helper(Node root){
if(root == null) return ;
res.add(root.val);
for(Node child: root.children){
helper(child);
}
} List<Integer> res = new ArrayList<>();
public List<Integer> postorder(Node root) {
dfs(root);
return res;
}
private void dfs(Node root) {
if (root == null) {
return;
}
// 遍历root的所有的children
for (Node child : root.children) {
dfs(child);
}
// 后序遍历开始添加
res.add(root.val);
}方法1:迭代-标识节点
public String tree2str(TreeNode t) {
//标识节点
TreeNode end = new TreeNode(-1);
StringBuilder sb = new StringBuilder();
Deque<TreeNode> stk = new ArrayDeque<>();
stk.push(t);
while (!stk.isEmpty()) {
TreeNode node = stk.pop();
if (node == end) {//当当前节点是标识节点，开始添加右括号
sb.append(')');
continue;
}
sb.append('(').append(node.val);
stk.push(end);
//当前节点的的左节点空，右节点非空，左节点加"()"
if (node.left == null && node.right != null) sb.append("()");
//左节点先出栈，入的时候先入右节点，后入左节点
if (node.right != null) stk.push(node.right);
if (node.left != null) stk.push(node.left);
}
//去掉首位
return sb.substring(1, sb.length() - 1);
}方法2:迭代-Set
public String tree2str(TreeNode t) {
StringBuilder sb = new StringBuilder();
Deque<TreeNode> stk = new ArrayDeque<>();
stk.push(t);
//使用set来标识是否访问过，控制")"边界
Set<TreeNode> vis = new HashSet<>();
while (!stk.isEmpty()) {
TreeNode node = stk.pop();
if (vis.contains(node)) {
sb.append(')');
continue;
}
sb.append('(').append(node.val);
stk.push(node);
//当前节点的的左节点空，右节点非空，左节点加"()"
if (node.left == null && node.right != null) sb.append("()");
//左节点先出栈，入的时候先入右节点，后入左节点
if (node.right != null) stk.push(node.right);
if (node.left != null) stk.push(node.left);
vis.add(node);
}
//去掉首位
return sb.substring(1, sb.length() - 1);
}方法3:递归
public String tree2str(TreeNode t) {
if (t == null) return "";//当前节点为空，返回""
if (t.left == null && t.right == null) return t.val + "";//当前节点没有左右孩子节点，即叶子节点，返回这个值
if (t.right == null) return t.val + "(" + tree2str(t.left) + ")";//当前节点只有左孩子，没有右孩子，给左孩子加上"()",右孩子不加
return t.val + "(" + tree2str(t.left) + ")" + "(" + tree2str(t.right) + ")";//左孩子有或者没有都加 "()" || "(leftChild)"
}方法1:递归+Set
Set<Integer> set = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
if(root == null) return false;
if(set.contains(k - root.val)) return true;
set.add(root.val);
return findTarget(root.left,k) || findTarget(root.right,k);
}方法2:双指针
//[5,3,6,2,4,null,7]
//k =11
public boolean findTarget(TreeNode root, int k) {
//左右两个子树的queue
Deque<TreeNode> lq = new ArrayDeque<>();
Deque<TreeNode> rq = new ArrayDeque<>();
TreeNode t = root;
//一直压左子树 [2,3,5]
while (t != null) {
lq.addLast(t);
t = t.left;
}
t = root;
//一直压右子树 [7,6,5]
while (t != null) {
rq.addLast(t);
t = t.right;
}
//第一次进来 ln =2 ,rn = 7 一个是lq的最小值， 一个是rq的最大值
TreeNode ln = lq.peekLast();
TreeNode rn = rq.peekLast();
while (ln.val < rn.val) {
//模拟双指针
int sum = ln.val + rn.val;
if (sum == k) return true;
//如果sum小了，挪动左指针 sum大了 挪动有右指针
if (sum < k) ln = getNext(lq, true);
else rn = getNext(rq, false);
}
return false;
}
public TreeNode getNext(Deque<TreeNode> q, boolean f) {
//如果是左子树，拿到左子树的右节点，如果是右子树，拿到右子树的左节点
TreeNode t = f ? q.pollLast().right : q.pollLast().left;
//一直添加该节点的左 / 右 子树的节点
while (t != null) {
q.addLast(t);
t = f ? t.left : t.right;
}
return q.peekLast();
}方法1：递归
public boolean isUnivalTree(TreeNode root) {
if (root == null) return false;
return dfs(root, root.val);
}
private boolean dfs(TreeNode root, int val) {
if (root == null) return true;
if (root.val != val) return false;
return dfs(root.left, val) && dfs(root.right, val);
}不带
helper函数：
public boolean isUnivalTree(TreeNode root) {
if (root == null) return true;
if (root.left != null && root.left.val != root.val) return false;
if (root.right != null && root.right.val != root.val) return false;
return isUnivalTree(root.left) && isUnivalTree(root.right);
}方法2：迭代
public boolean isUnivalTree(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (cur.val != root.val) return false;
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
return true;
}方法1：递归
int res;
public int sumRootToLeaf(TreeNode root) {
dfs(root, new ArrayList<>());
return res;
}
public void dfs(TreeNode root, List<Integer> paths) {
paths.add(root.val);
if (root.left == null && root.right == null) {
res += cal(paths);
return;
}
if (root.left != null) {
dfs(root.left, paths);
paths.remove(paths.size() - 1);
}
if (root.right != null) {
dfs(root.right, paths);
paths.remove(paths.size() - 1);
}
}
private int cal(List<Integer> paths) {
int t = 0, n = paths.size();
for (int i = 0; i < n; i++) {
t |= paths.get(i) << (n - i - 1);
}
return t;方法2：递归
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int res) {
if (root == null) return 0;
//res左移一位，让出低位给root.val
res = res << 1 | root.val;
if (root.left == null && root.right == null) {
return res;
}
return dfs(root.left, res) + dfs(root.right, res);
}方法3：迭代
迭代的思路不如递归好写
public int sumRootToLeaf(TreeNode root) {
Deque<TreeNode> stk = new ArrayDeque<>();
int t = 0, res = 0;
//prev记录上一轮访问过的节点
TreeNode prev = null;
while (!stk.isEmpty() || root != null) {
while (root != null) {
//计算
t = t << 1 | root.val;
//左孩子一直进栈，直到没有左孩子
stk.push(root);
root = root.left;
}
//看下当前栈顶的节点
root = stk.peek();
//
if (root.right == null || root.right == prev) {
//收集的条件
if (root.left == null && root.right == null) {
res += t;
}
//恢复，弹出，记录prev
t >>= 1;
stk.pop();
prev = root;
root = null;//标记
} else {
root = root.right;
}
}
return res;
}方法1：中序+归并
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>(), list2 = new ArrayList<>(), res = new ArrayList<>();
inOrder(root1, list1);
inOrder(root2, list2);
int p1 = 0, p2 = 0;
while (true) {
if (p1 == list1.size()) {
res.addAll(list2.subList(p2, list2.size()));
break;
}
if (p2 == list2.size()) {
res.addAll(list1.subList(p1, list1.size()));
break;
}
if (list1.get(p1) <= list2.get(p2)) {
res.add(list1.get(p1++));
} else {
res.add(list2.get(p2++));
}
}
return res;
}
private void inOrder(TreeNode root, List<Integer> list) {
if (root != null) {
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
}
}方法2:BFS
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stk1 = new ArrayDeque<>(), stk2 = new ArrayDeque<>();
TreeNode cur1 = root1, cur2 = root2;
while (cur1 != null || cur2 != null || !stk1.isEmpty() || !stk2.isEmpty()) {
while (cur1 != null) {
stk1.push(cur1);
cur1 = cur1.left;
}
while (cur2 != null) {
stk2.push(cur2);
cur2 = cur2.left;
}
//注意当stk2是空的时候，将stk1的元素全部pop出来即可
if (stk2.isEmpty() || !stk1.isEmpty() && stk1.peek().val < stk2.peek().val) {
cur1 = stk1.pop();
res.add(cur1.val);
cur1 = cur1.right;
} else {
cur2 = stk2.pop();
res.add(cur2.val);
cur2 = cur2.right;
}
}
return res;
}另一种写法
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stk1 = new ArrayDeque<>(), stk2 = new ArrayDeque<>();
pushLeft(stk1, root1);
pushLeft(stk2, root2);
while (!stk1.isEmpty() || !stk2.isEmpty()) {
Deque<TreeNode> stk;
if (stk1.isEmpty()) stk = stk2;
else if (stk2.isEmpty()) stk = stk1;
else stk = stk1.peek().val < stk2.peek().val ? stk1 : stk2;
TreeNode cur = stk.pop();
res.add(cur.val);
pushLeft(stk, cur.right);
}
return res;
}
private void pushLeft(Deque<TreeNode> stk, TreeNode root) {
while (root != null) {
stk.push(root);
root = root.left;
}
}另另外一种写法
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stk1 = new ArrayDeque<>(), stk2 = new ArrayDeque<>();
pushLeft(stk1, root1);
pushLeft(stk2, root2);
while (!stk1.isEmpty() && !stk2.isEmpty()) {
if (stk1.peek().val < stk2.peek().val) {
res.add(next(stk1));
} else {
res.add(next(stk2));
}
}
while (!stk1.isEmpty()) res.add(next(stk1));
while (!stk2.isEmpty()) res.add(next(stk2));
return res;
}
private void pushLeft(Deque<TreeNode> stk, TreeNode root) {
while (root != null) {
stk.push(root);
root = root.left;
}
}
//先存右节点，再一直压左子树节点
private int next(Deque<TreeNode> stk) {
TreeNode cur = stk.pop();
int res = cur.val;
pushLeft(stk, cur.right);
return res;
}方法1：普通树+中序遍历
没有使用到二叉搜索树的性质
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode prev = null, cur = root;
while (!stk.isEmpty() || cur != null) {
while (cur != null) {
stk.push(cur);
cur = cur.left;
}
cur = stk.pop();
if (prev == p) return cur;
prev = cur;
cur = cur.right;
}
return null;
}另：
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
boolean f = false;
Deque<TreeNode> stk = new ArrayDeque<>();
while (!stk.isEmpty() || root != null) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
if (f) return root;
if (root.val == p.val) f = true;
root = root.right;
}
return null;
}方法2：迭代+二分
利用BST的性质
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode res = null;
while (root != null) {
//当前节点的值比p节点的值大，在当前节点的左子树上找，当前节点有可能是p节点的下一个节点，保存该节点
if (root.val > p.val) {
res = root;
root = root.left;
} else {//当前节点的值比p节点的值小或者相等（说明当前节点不是p节点的后继），在当前节点的右子树上继续找
root = root.right;
}
}
return res;
}方法3：递归
利用BST的性质
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null || p == null) {
return null;
}
//p节点的值比当前节点的值大或者相等，说明p节点的后继不可能在当前节点的左子树上（因为中序遍历的左子树的值比当前节点的值小）
//要设法去当前节点的右子树上找
if (root.val <= p.val) {
return inorderSuccessor(root.right, p);
} else {
//p节点的值比当前节点小了
//case1 left为null,说明在左子树上没找到，此时返回当前节点root
//case2 left不为null，说明找到了返回left
TreeNode left = inorderSuccessor(root.left, p);
return left == null ? root : left;
}
}方法1：遍历
找递增的两个点之间
找旋转点
public ListNode insert(ListNode head, int insertVal) {
if (head == null) {
ListNode insertNode = new ListNode(insertVal);
insertNode.next = insertNode;
return insertNode;
}
ListNode cur = head;
while (cur.next != head) {
if (cur.val < cur.next.val) {
if (insertVal >= cur.val && insertVal <= cur.next.val) {
insert(insertVal, cur);
return head;
}
}
if (cur.val > cur.next.val) {
if ((insertVal < cur.val && insertVal < cur.next.val) || insertVal > cur.val) {
insert(insertVal, cur);
return head;
}
}
cur = cur.next;
}
insert(insertVal, cur);
return head;
}
private static void insert(int insertVal, ListNode cur) {
ListNode insertNode = new ListNode(insertVal);
ListNode nxt = cur.next;
cur.next = insertNode;
insertNode.next = nxt;
}Last updated