Hov's Blog

To code, To record, To recall.

【LeetCode】94. Binary Tree Inorder Traversal

题目描述: Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree [1,null,2,3], 1 \ 2 / 3 return [1,3,2]. 思路: 二叉树的中序遍历,这里直接用递归的方法求解。 代码实现: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<Integer>(); inorder(root,ret); return ret; } public void inorder(TreeNode root, List<Integer> ret){ if(root==null){ return ; } inorder(root.

【LeetCode】75. Sort Colors

题目描述: Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library’s sort function for this problem. 思路: 本题实质上为三元数组排序。

【LeetCode】116. Populating Next Right Pointers in Each Node

题目描述: Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

【LeetCode】88. Merge Sorted Array

题目描述: Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively. 思路: 从后往前遍历两个数组,分别比较,大的放在数组 nums1 后面,直到两个数组都遍历完毕。 注:如果从前往后遍历的话,数组合并时需要将元素后移,效率低。 代码实现: class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int index = m+n-1; int i1 = m-1; int i2 = n-1; while(i1>=0&&i2>=0){ if(nums1[i1]>=nums2[i2]){ nums1[index] = nums1[i1]; i1--; }else{ nums1[index] = nums2[i2]; i2--; } index--; } while(i1>=0){ nums1[index] = nums1[i1]; i1--; index--; } while(i2>=0){ nums1[index] = nums2[i2]; i2--; index--; } } }

【LeetCode】83. Remove Duplicates from Sorted List

题目描述: Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. 思路: 遍历一次链表即可,每遍历一个元素比较其是否与它的下一个元素相等。若是,指针指向下下个元素;否则继续遍历下一个元素。 代码实现: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null){ return null; } ListNode p = head; while(p.