671. 二叉树中的第二小节点
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
示例 1:
输入:
2
/
2 5
/
5 7
输出: 5
// 二叉树中第二小的节点,这个树的定义实质就是最小堆，第一个比最小值大的就是第二小
public int findSecondMinimumValue(TreeNode root) {
if(root == null){
return -1;
}
return helper(root,root.val);
}
public int helper(TreeNode root, int min){
if(root == null){
return -1;
}
if(root.val > min){
return root.val;
}
// 左右子树中第一个比最小值大的数
int left = helper(root.left,min);
int right = helper(root.right,min);
if(left == -1){
return right;
}
if(right == -1){
return left;
}
return Math.min(left,right);
}
144. 二叉树的前序遍历
List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return res;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
res.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
非递归
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
return res;
}
94. 二叉树的中序遍历
// 中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(!stack.empty() || cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
145. 二叉树的后序遍历
// 后续遍历就是前序遍历，每次向头进行添加
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
res.add(0,node.val);
if(node.left != null){
stack.push(node.left);
}
if(node.right != null){
stack.push(node.right);
}
}
return res;
}
33. 剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
// 验证是否是后序遍历
// 找到第一个小于其的左边都是小于其的
public boolean verifyPostorder(int[] postorder) {
if(postorder == null || postorder.length == 0){
return true;
}
return verifyPostorder(postorder,0,postorder.length-1);
}
public boolean verifyPostorder(int[] postorder, int left, int right){
if(left >= right){
return true;
}
int p = left;
while(postorder[p] < postorder[right]) p++;
int m = p;
while(postorder[p] > postorder[right]) p++;
return p == right && verifyPostorder(postorder,left,m-1) && verifyPostorder(postorder,m,right-1);
}
105. 从前序和中序创建二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(inorder == null || inorder.length == 0){
return null;
}
return buildTree(preorder,0,preorder.length-1, inorder, 0, inorder.length-1);
}
public TreeNode buildTree(int[] preorder, int s1, int e1, int[] inorder , int s2, int e2){
if(s1 > e1){
return null;
}
int val = preorder[s1];
TreeNode root = new TreeNode(val);
int index = getIndex(inorder,s2,e2,val);
int leftLen = index - s2;
root.left = buildTree(preorder,s1+1,s1 + leftLen,inorder,s2,index-1);
root.right = buildTree(preorder,s1 + leftLen + 1,e1,inorder,index+1,e2);
return root;
}
public int getIndex(int[] inorder, int left, int right,int k){
for(int i=left;i<=right;i++){
if(inorder[i] == k){
return i;
}
}
return -1;
}
106. 从中序与后序遍历构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder == null || inorder.length == 0){
return null;
}
return buildTree(inorder,0,inorder.length-1, postorder,0,postorder.length-1);
}
public TreeNode buildTree(int[] inorder,int s1, int e1, int[] postorder, int s2, int e2){
if(s1 > e1 || s2 > e2){
return null;
}
int val = postorder[e2];
TreeNode root = new TreeNode(val);
int index = getIndex(inorder,s1,e1,val);
int leftLen = index - s1;
root.left = buildTree(inorder,s1,index-1,postorder,s2,s2+leftLen-1);
root.right = buildTree(inorder,index+1,e1,postorder,s2+leftLen,e2-1);
return root;
}
public int getIndex(int[] inorder, int left , int right , int k){
for(int i=left;i<=right;i++){
if(k == inorder[i]){
return i;
}
}
return -1;
}
110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
// 判断是否是平衡二叉树，先要求树的高度
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
boolean left = isBalanced(root.left);
if(left == false){
return false;
}
boolean right = isBalanced(root.right);
if(right == false){
return false;
}
int lh = treeHeight(root.left);
int rh = treeHeight(root.right);
if(Math.abs(lh - rh) < 2){
return true;
}
return false;
}
public int treeHeight(TreeNode root){
if(root == null){
return 0;
}
return 1 + Math.max(treeHeight(root.left),treeHeight(root.right));
}
98.验证二叉树中序遍历
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/
1 3
输出: true
// 进行中序遍历即可
Integer pre = null;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
return inorder(root);
}
public boolean inorder(TreeNode root){
if(root == null){
return true;
}
boolean left = inorder(root.left);
if(left == false){
return false;
}
if(pre != null && pre >= root.val){
return false;
}
pre = root.val;
boolean right = inorder(root.right);
if(right == false){
return false;
}
return true;
}
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
// 1. 先判断根节点是否是公共
if(root == p || root == q){
return root;
}
// 2. 左右两孩子是公共，根是公共
if(left != null && right != null){
return root;
}
// 3. 判断子树
if(left != null){
return left;
}
if(right != null){
return right;
}
return null;
}
68. 二茬搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null){
if(root.val < p.val && root.val < q.val){
root = root.right;
}else if(root.val > p.val && root.val > q.val){
root = root.left;
}else{
return root;
}
}
return null;
}
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
二叉树的最小深度，是在左右子树存在一个为null,那就是最大深度，否则是最小深度
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
if(root.left == null || root.right == null){
return 1 + Math.max(minDepth(root.left), minDepth(root.right));
}
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
257.二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/
2 3
5
// 二叉树的所有路径,先序遍历
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if(root == null){
return res;
}
String path = root.val + "";
Stack<String> stack_path = new Stack<>();
Stack<TreeNode> stack = new Stack<>();
stack_path.push(path);
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
path = stack_path.pop();
if(node.left == null && node.right == null){
res.add(path);
}
if(node.right != null){
stack_path.push(path + "->" + node.right.val);
stack.push(node.right);
}
if(node.left != null){
stack_path.push(path + "->" + node.left.val);
stack.push(node.left);
}
}
return res;
}
// 二叉树的所有路径,先序遍历
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
rebuildPath(root,"",res);
return res;
}
public void rebuildPath(TreeNode root, String path, List<String> res){
if(root == null){
return;
}
path += root.val + "";
if(root.left == null && root.right == null){
res.add(path);
}
path += "->";
rebuildPath(root.left,path,res);
rebuildPath(root.right,path,res);
}
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
return hasPathSum(root,0,sum);
}
public boolean hasPathSum(TreeNode root, int x, int sum){
if(root == null){
return false;
}
x += root.val;
if(root.left == null && root.right == null){
if(x == sum){
return true;
}
}else{
boolean left = hasPathSum(root.left,x,sum);
if(left == true){
return true;
}
boolean right = hasPathSum(root.right,x,sum);
if(right == true){
return true;
}
}
return false;
}
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
if(root.left == null && root.right == null){
if(sum - root.val == 0){
return true;
}
}
return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
}
113. 路径总和2
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
hasPathSum(root,0,sum,new ArrayList<>());
return res;
}
public void hasPathSum(TreeNode root, int x, int sum, List<Integer> list){
if(root == null){
return;
}
x += root.val;
list.add(root.val);
if(root.left == null && root.right == null){
if(x == sum){
res.add(new ArrayList<>(list));
}
}else{
hasPathSum(root.left,x,sum,list);
hasPathSum(root.right,x,sum,list);
}
// 进行回溯
list.remove(list.size()-1);
}
437. 路径总和3
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
// 将每一个节点视为一颗树
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
return pathSumCore(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
}
public int pathSumCore(TreeNode root, int sum){
if(root == null){
return 0;
}
int res = 0;
if(sum - root.val == 0){
res ++;
}
res += pathSumCore(root.left,sum - root.val);
res += pathSumCore(root.right,sum - root.val);
return res;
}
最长不含有重复串的字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 思路是使用 hashmap 进行存储，之前的位置
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0){
return 0;
}
HashMap<Character,Integer> map = new HashMap<>();
int max = 1;
int left = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(map.containsKey(c) && map.get(c) > left){
max = Math.max(i-left,max);
left = map.get(c);
}
map.put(c,i+1);
}
return Math.max(s.length()-left,max);
}
315. 计算右侧小于当前元素的个数
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
// 计算右侧小于当前元素的个数，
// 可以从右边开始进行而进制的插入排序，插入的位置就是
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0){
return res;
}
List<Integer> list = new ArrayList<>();
for(int i = nums.length -1;i >= 0;i--){
int left = 0, right = list.size();
while(left < right){
int mid = left + (right - left)/2;
if(list.get(mid) >= nums[i]){
right = mid;
}else{
left = mid + 1;
}
}
list.add(left, nums[i]);
res.add(left);
}
Collections.reverse(res);
return res;
}
442. 数组中的重复数据
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
// 这里因为 数值都是 1~n 可以将其散列在长度为n的数组中
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0){
return res;
}
int n = nums.length;
// 可以将字符的添加增加到遍历中
for(int x: nums){
int index = Math.abs(x) - 1;
nums[index] = -nums[index];
if(nums[index] > 0){
res.add(Math.abs(x));
}
}
return res;
}
189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
// 将数组进行三次反转
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
reserve(nums,0,nums.length-k-1);
reserve(nums,nums.length-k,nums.length-1);
reserve(nums,0,nums.length-1);
}
public void reserve(int[] nums, int left, int right){
while(left < right){
swap(nums,left,right);
left++;
right--;
}
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
31. 下一次排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
public void nextPermutation(int[] nums) {
nextPermutation(nums,0,nums.length);
}
private void nextPermutation(int[] nums, int start, int end) {
int p = end -2;
while (p > -1 && nums[p] >= nums[p+1]){
p--;
}
if (p == -1){
reverse(nums,0,end);
return;
}
int c = end - 1;
while (c > p && nums[c] <= nums[p]){
c--;
}
swap(nums,p,c);
reverse(nums,p+1,end);
return;
}
private void swap(int[] nums, int p, int c) {
int tmp = nums[c];
nums[c] = nums[p];
nums[p] = tmp;
}
private void reverse(int[] nums, int start, int end) {
for (int i = 0;i<(end - start)/2;i++){
int tmp = nums[start + i];
nums[start + i] = nums[end - i -1];
nums[end - i - 1] = tmp;
}
915. 分割数组
给定一个数组 A，将其划分为两个不相交（没有公共元素）的连续子数组 left 和 right， 使得：
left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 要尽可能小。
在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。
示例 1：
输入：[5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]
// 因为数组的顺序是不能够改变的，所以思路是采用两个数组，将从左到右，从右到左的小数组
public int partitionDisjoint(int[] A) {
if(A == null || A.length == 0){
return 0;
}
int[] leftMax = new int[A.length];
int[] rightMin = new int[A.length];
int max = A[0];
for(int i=0;i<A.length;i++){
max = Math.max(A[i], max);
leftMax[i] = max;
}
int min = A[A.length-1];
for(int i=A.length-1;i>=0;i--){
min = Math.min(A[i],min);
rightMin[i] = min;
}
for(int i=0;i<A.length-1;i++){
if(leftMax[i] <= rightMin[i+1]){
return i+1;
}
}
return -1;
}
54. 矩阵旋转
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
// 思路是，定义左上角和右下角位置，每次进行缩减, 只需要多住一个一个情况柱状模式
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int leftUpRow = 0, leftUpCol = 0;
int rightDownRow = matrix.length -1, rightDownCol = matrix[0].length - 1;
int r = 0, c = 0;
while(leftUpRow <= rightDownRow && leftUpCol <= rightDownCol){
r = leftUpRow;
c = leftUpCol;
while(c <= rightDownCol){
res.add(matrix[leftUpRow][c]);
c++;
}
c--;
r++;
while(r <= rightDownRow){
res.add(matrix[r][rightDownCol]);
r++;
}
r--;
c--;
while(c >= leftUpCol && leftUpRow != rightDownRow){
res.add(matrix[rightDownRow][c]);
c--;
}
c++;
r--;
while(r > leftUpRow && leftUpCol != rightDownCol){
res.add(matrix[r][leftUpCol]);
r--;
}
leftUpCol++;
leftUpRow++;
rightDownCol--;
rightDownRow--;
}
return res;
}
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 使用dp
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int maxSum = Integer.MIN_VALUE;
int curSum = 0;
for(int x : nums){
if(curSum < 0){
curSum = x;
}else{
curSum += x;
}
maxSum = Math.max(curSum, maxSum);
}
return maxSum;
}
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
// dp , 同时记录最大和最小，当前值为负数是交换
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int max = 1;
int min = 1;
int maxProduct = Integer.MIN_VALUE;
for(int x : nums){
if(x < 0){
int tmp = min;
min = max;
max = tmp;
}
min = Math.min(min * x,x);
max = Math.max(max * x,x);
maxProduct = Math.max(maxProduct,max);
}
return maxProduct;
}
138.复制带有随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
// 复制带有随机指针的链表
// 使用hashmap 进行复制节点，同时按照链表顺序间next和随机节点连接起来
public Node copyRandomList(Node head) {
if(head == null){
return head;
}
HashMap<Node, Node> map = new HashMap<>();
Node p = head;
while(p != null){
map.put(p, new Node(p.val));
p = p.next;
}
p = head;
while(p != null){
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(head);
}
136.
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
// 异或将相同的数约掉
public int singleNumber(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int res = 0;
for(int x: nums){
res ^= x;
}
return res;
}
网友评论