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], [] […]