Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. Show Tags //preorder储存数字信息 //inorder存储结构信息 //每次inorder都会把数平分成两半 //注意不要内存超界。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode […]
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 […]
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 […]
Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = “aabcc”, s2 = “dbbca”, When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false. //方案一，递归，超时。复杂度o(n+m) class Solution { public: bool isInterleave(string s1, string s2, string […]
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 […]
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 […]
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 = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] […]
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 […]
There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an […]
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. 困倦时不要解题，这题做了3遍才AC。 一个bonus，删掉多余的node，以免内存溢出。 我用了superHead的技巧，不用再单独判断链表的起始情况。 查看当前节点和下一个节点，如果相同，将isDuplicated置1.当遇到当前节点和下一节点不同时，看isDuplicated的值，如果是1，则忽略掉它，把isDuplicated置0.如果是0，证明当前节点没有重复，连入结果链表中。 /** * Definition for singly-linked list. * struct ListNode { […]
