数据结构算法（链表、二叉树的各种算法）

数组

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

数组中有重复元素，可以考虑利用Set集合的特性，不可以有重复元素

class Solution { public int findRepeatNumber(int[] nums) { //使用Set，无重复元素，添加重复元素，add失败 Set<Integer> set = new HashSet<>(); int res = -1; for(int num : nums) { if(!set.add(num)) { res = num; break; } } return res; } } 

能利用数组下标，注意利用数组下标

class Solution { public int findRepeatNumber(int[] nums) { //利用数组的下标 //注意读题，所有元素范围都在0~n-1，排序过后，数组下标对应数组元素 int temp; for(int i=0;i<nums.length;i++){ //交换直到数组下标和数组元素对应 while (nums[i]!=i){ //0 1 2 3 2 //nums[4] = nums[nums[4]] = nums[2] = 2发现重复元素返回 if(nums[i]==nums[nums[i]]){ return nums[i]; } temp=nums[i]; nums[i]=nums[temp]; nums[temp]=temp; } } return -1; } } 

二分法的使用

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

class Solution { public int search(int[] nums, int target) { //找到target所在位置，start //找到target+1所在位置,end //end-start+(1/0) if(nums == null || nums.length==0) return 0; int start = binarySearch(nums, target); int end = binarySearch(nums, target+1); return end - start + (nums[end] == target ? 1 : 0); } //二分 private int binarySearch(int[] nums, int tar) { int l=0,r=nums.length-1; while(l<r) { //int mid = (l+r)/2; int mid = l + (r-l)/2;//防止int类型溢出 if(nums[mid] < tar) { l = mid + 1; }else{ r = mid; } } return l; } } 

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2
示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

class Solution { public int missingNumber(int[] nums) { //二分法 if(nums == null || nums.length==0) return 0; int l = 0,r = nums.length - 1; while(l<r) { int mid = l+(r-l)/2; if(nums[mid] != mid) r=mid; else l=mid+1; } //特殊情况[0,1,2]缺少的是3 if(nums[r] == r) r++; return r; } } 

链表

单链表删除结点

找到cur的上一个结点pre及下一个结点next,pre.next=cure.next

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */ //给定头指针和要删除的结点的值，删除该节点，返回删除后的头结点 class Solution { public ListNode deleteNode(ListNode head, int val) { //如果删除的是第一个结点，则直接删除第一个结点 if(head.val == val) return head.next; //删除单链表的结点，查找要删除的结点cur,pre是前一个结点 ListNode pre = head; ListNode cur = head.next; //找到val结点 while(cur.val != val && cur != null) { pre = cur; cur = cur.next; } //找到后，删除结点 if(cur != null) { pre.next = cur.next; } return head; } } 

虚拟头结点的使用，有时候用虚拟头结点更方便。定义一个虚拟头结点dummy,dummy.next=head;

ListNode dummy = new ListNode(0); dummy.next = head; 

双指针的使用，灵活使用双指针，会带来很多方便

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */ //输出链表倒数的第k个结点 class Solution { public ListNode getKthFromEnd(ListNode head, int k) { //双指针 ListNode first = head; ListNode second = head; for(int i=0; i<k; i++) { //k大于链表的长度 if(first == null) return null; first = first.next; } while(first != null) { first = first.next; second =second.next; } return second; } } 

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur != null) { //cur往后走，先将pre原来的结点保存，cur.next=pre，然后cur指向pre,pre=cur //1 2 3 4 5 null //第一次 //pre=null cur=1 //cur=2 pre=1->null //第二次 //cur=3 pre=2->1->null //第三次 //cur=4 pre=3->2->1->null ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } } 

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表**：**

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */ //从a1出发，跑到最后再从b1开始跑 //从b1出发，跑到最后再从a1开始跑 //他们肯定会在c1相遇，路程一样 //a1 a2 c1 c2 c3 b1 b2 b3 c1 路程9 //b1 b2 b3 c1 c2 c3 a1 a2 c1 路程9 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode indexA = headA; ListNode indexB = headB; while(indexA != indexB) { if(indexA == null) indexA = headB; else indexA = indexA.next; if(indexB == null) indexB = headA; else indexB = indexB.next; } return indexA; } } 

树

树的基本方法就是递归

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

 3
   / \
   4  5
  / \
 1   2 

给定的树 B：

 4 
  /
 1 

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { //递归 //A根 B根 //A左子树 B //A右子树 B return (A!=null && B!=null) && (isSubTree(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B)); } public boolean isSubTree(TreeNode A, TreeNode B) { if(B == null) return true; if(A == null || A.val != B.val) return false; return isSubTree(A.left,B.left) && isSubTree(A.right,B.right); } } 

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

 4
   /   \
  2     7
 / \   / \
1   3 6   9 

镜像输出：

 4
   /   \
  7     2
 / \   / \
9   6 3   1 

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public TreeNode mirrorTree(TreeNode root) { //左右子树交换 if(root == null) return null; TreeNode temp = root.left; root.left = mirrorTree(root.right); root.right = mirrorTree(temp); return root; } } 

剑指 Offer 28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

 1
   / \
  2   2
 / \ / \
3  4 4  3 

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

 1
   / \
  2   2
   \   \
   3    3 

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return dfs(root.left, root.right); } public boolean dfs(TreeNode left, TreeNode right) { if(left == null && right == null) return true; if(left == null || right == null || left.val != right.val) return false; return dfs(left.left, right.right) && dfs(left.right, right.left); } } 

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1

 3
  / \
 1   4
  \
   2 

输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

 5
      / \
     3   6
    / \
   2   4
  /
 1 

输出: 4

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { //二叉搜索树，中序排序递增，左 根 右 //反过来递减，右 根 左 int k1,res; public int kthLargest(TreeNode root, int k) { k1 = k; dfs(root); return res; } private void dfs(TreeNode root) { if(root == null || k1 == 0) return; //右子树 dfs(root.right); //根节点 k1 -= 1; if(k1 == 0) res = root.val; //左子树 dfs(root.left); } } 

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

 3
   / \
  9  20
    /  \
   15   7 

返回它的最大深度 3 。

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；

常见的 DFS ： 先序遍历、中序遍历、后序遍历（左右根）；
常见的 BFS ： 层序遍历（即按层遍历）。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { //后序遍历dfs public int maxDepth1(TreeNode root) { if(root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } //层次遍历bfs，借助列表 public int maxDepth(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if(root !=null) queue.add(root); int res = 0; while(!queue.isEmpty()) { int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.poll(); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res++; } return res; } } 

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

 3
   / \
  9  20
    /  \
   15   7 

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

 1
      / \
     2   2
    / \
   3   3
  / \
 4   4 

返回 false 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { //求深度 public int treeDepth(TreeNode root) { if(root == null) return 0; int left = treeDepth(root.left); int right = treeDepth(root.right); return left>right ? left+1 : right+1; } //深度差<=1 public boolean isBalanced(TreeNode root) { if(root == null) return true; int left = treeDepth(root.left); int right = treeDepth(root.right); //abs取绝对值 return Math.abs(left-right)>1 ? false : true && isBalanced(root.left) && isBalanced(root.right); } } 

借助队列和链表实现树的层次遍历

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

 3
   / \
  9  20
    /  \
   15   7 

返回：

[3,9,20,15,7]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public int[] levelOrder(TreeNode root) { //用队列保存根节点，用int[]记录返回的数组 if(root == null) return new int[0]; ArrayList<Integer> arr = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()) { //借助队列 //根节点,poll检索并删除队列头，并返回结点，将val添加到链表中 //如果结点有子树，则继续添加到队列，如果队列为空，说明树已经遍历完成 TreeNode r = queue.poll(); arr.add(r.val); //左子树 if(r.left != null) queue.add(r.left); //右子树 if(r.right != null) queue.add(r.right); } //通过链表获取要返回的数组长度，并将链表中的元素添加到数组中 int[] res = new int[arr.size()]; for(int i=0; i<arr.size();i++) { res[i] = arr.get(i); } return res; } } 

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

 3
   / \
  9  20
    /  \
   15   7 

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
] 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>();//[[]] Queue<TreeNode> queue = new LinkedList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { //借助队列和链表实现树的层次遍历 List<Integer> temp = new ArrayList<>(); int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.poll(); temp.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(temp); } return res; } } 

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

 3
   / \
  9  20
    /  \
   15   7 

返回其层次遍历结果：

[
  [3],
  [20,9],
  [15,7]
] 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>();//[[]] Queue<TreeNode> queue = new LinkedList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { //addlast在列表结尾插入，addfirst在列表开头插入 LinkedList<Integer> temp = new LinkedList<>(); int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.poll(); //判断，当前在奇数层还是偶数层 //奇数层在开头插入，逆序 //偶数层，在结尾插入，顺序 if(res.size() % 2 == 0) { temp.addLast(node.val); }else{ temp.addFirst(node.val); } if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(temp); } return res; } } 

利用先序遍历和递归

剑指 Offer 34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

 5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1 

返回:

[
   [5,4,11,2],
   [5,8,4,5]
] 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ class Solution { //利用前序遍历，根左右 //保存所有路径 LinkedList<List<Integer>> res = new LinkedList<>(); //保存单条路径 LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { recur(root, sum); return res; } void recur(TreeNode root, int target) { //找到target=0时的叶结点 if(root == null) return; path.add(root.val); target -= root.val; if(target == 0 && root.left==null && root.right==null) res.add(new LinkedList(path)); recur(root.left, target); recur(root.right, target); //每次结束后，都要把path清空 path.removeLast(); } } 

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

 1
   / \
  2   3
     / \
    4   5 

序列化为 “[1,2,3,null,null,4,5]”

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return "[]"; //[1,2,3,null,null,4,5] StringBuilder res = new StringBuilder("["); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()) { TreeNode t = queue.poll(); if(t!=null) { res.append(t.val+","); queue.add(t.left); queue.add(t.right); }else { res.append("null,"); } } res.append("]"); return res.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.equals("[]")) return null; //substring(begin,end),左闭右开 String[] vals = data.substring(1,data.length()-1).split(","); //parseInt()将字符串参数解析为int TreeNode root = new TreeNode(Integer.parseInt(vals[0])); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int i = 1; while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(!vals[i].equals("null")) { node.left = new TreeNode(Integer.parseInt(vals[i])); queue.add(node.left); } i++; if(!vals[i].equals("null")) { node.right = new TreeNode(Integer.parseInt(vals[i])); queue.add(node.right); } i++; } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root)); 

本文地址：https://blog.csdn.net/qq_35396093/article/details/107891730