ITeye博客

2016 年文章归档

共 209 篇文章

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 给定一个单向有序的列表,将它转换成一颗平衡二叉搜索树。我们采用快慢指针,然后确定链表中的中间节点,将中间作为当前子树的根节点,然后将链表分为两段,递归完成。代码如下: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode…

2016-02-08 05:30 · Leetcode

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 给定一个排好序的数组,构造一颗平衡的二叉搜索树。我们可以每次都取数组的中间点作为当前子树的根节点,递归完成。代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x;…

2016-02-08 05:13 · Leetcode

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. 用后序遍历序列来确定根节点的位置,然后在中序遍历中确定左右子树,递归完成树的构造。代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; …

2016-02-08 05:02 · Leetcode

Construct Binary Tree from Preorder and Inorder Traversal

iven preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. 给定一棵树的中序遍历和前序遍历,构造出这棵树。我们可以通过前序遍历序列的第一个元素判断出每个子树的根节点,然后在中序遍历序列找到这个根节点,假设这个根结点在i位置,那么在inorder 左边的就是左子树的元素,在inorder 右边的就是右子树的元素。用递归来完成。代码如下: /** * Definition for a …

2016-02-08 04:29 · Leetcode

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 return its bottom-up level order traversal as: , , ] 同样是二叉树广度优先遍历的变形,要求从下面开始记录每一层的节点,我们…

2016-02-07 05:16 · Leetcode

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 return its zigzag level order traversal as: , , ] Binary Tree L…

2016-02-07 05:03 · Leetcode

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7 return its level order traversal as: , , ] 二叉树的广度优先搜索,用队列来实现,借助两个变量来记录每一层的节点个数,以及何时将每层的节点的值加入到结果集中。代码如下: /** * Defi…

2016-02-07 04:47 · Leetcode

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1 / 2 2 / \ / 3 4 4 3 But the following is not: 1 / 2 2 \ 3 3 判定一棵树是不是对称的,和 Same Tree 这道题思想一样,same tree是判断两个数是不是一样,这道题目是判断左子树是不是右子树的镜像,用递归解决。代码如下: /** * Definit…

2016-02-07 04:30 · Leetcode

Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n. For example, Given n = 3, your program should return all 5 unique BST's shown below. 1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3 与 Unique Binary Search Trees 相比这道题目要难一些,要求输出所有可能的二叉查找树。在for循环中用递归解决。代码如下:…

2016-02-07 04:16 · Leetcode

Same Tree

Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. 给定两颗二叉树,判断这两颗树是否相同,它们相同的条件是结构相同,对应节点的值也必须相同。同样采用递归的方式,先比较对应点的节点是否为空,如果都为空,那么在当前状态下返回true;如果一个空,一个不为空,返回false。如果都不为空…

2016-02-06 12:35 · Leetcode

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and r…

2016-02-06 11:35 · Leetcode

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example, Given n = 3, there are a total of 5 unique BST's. 1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3 考察二叉树的种类,卡特兰数的例子。这里要注意的是空树也属于二叉搜索树。代码如下: public class Solution { public int numTrees(int n) { int[]…

2016-02-06 11:12 · Leetcode

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 2 / 3 return . 中序遍历一棵树,我们可以采用递归,也可以用迭代,用迭代的时候借助堆栈来完成。 1,递归 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(…

2016-02-06 10:46 · Leetcode

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. 用一个辅助节点helper找到m的位置,然后依次交换位置,代码如下: /** * Definition for sing…

2016-02-06 05:55 · Leetcode

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "…

2016-02-05 08:23 · Leetcode

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If nums = , a solution is: , , , , , ] 这道题目是 Subsets 的变形,数组中包含了重复的元素,之前介绍了两种…

2016-02-05 04:00 · Leetcode

Gray Code 格雷码

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return . Its gray code se…

2016-02-04 03:45 · Leetcode

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 respective…

2016-02-04 03:21 · Leetcode

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. 给定一个链表和一个…

2016-02-04 03:08 · Leetcode

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3. 与 Remove Duplicates from Sorted List 相比,这道题目要求删除所有重复的元素,这样头结点可能会被删除,我们这时同样需要创建一个辅…

2016-02-04 01:55 · Leetcode