leetCode解题报告5道题(五)

题目一：

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

AC代码：

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

分析：无情递归就OK了，递归结束的条件：当是叶子结点并且sum的值已经变成了0，这时候的List为一组有效的解，加入到结果集合result中。

题目二：

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

AC代码：

题目三：

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

分析：题目给我们一个二叉树的结构，让我们去判断这个二叉树是否是对称的。这道题目可以有两种做法，递归(424ms)或者用层次遍历树(524ms)的方法

这个题目的递归很容易就看出来了，我就不详细讲，具体看代码里面的注释理解！

（递归）AC代码（424ms）：

（层次遍历）AC代码(524ms):

题目四：

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

分析：仔细观察题目给出的例子，不难发现其实这个可以用递归来做，求root结点的flatten tree相当于先求出左子树，再求出右子树，然后将左子树的最后一个结点连接到右子树的第一个结点，将root的右子树连接到左子树的第一个结点上，总而言之这题还是比较简单的，建议做这题的时候可以在纸上画一下图，帮助理解！

1、root只有左子树

2、root只有右子树

3、root左右子树都有

AC代码：

题目五：

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

题意：求出字符串T在字符串S中出现的次数，

S字符串:

0 1  2  3  4  5  6

r  a  b  b  b  i   t

T字符串:

0 1  2  3  4   5 

r  a  b  b  i   t

出现的最大次数是3，三种情况分别为：

S: 0 1 2 3 5 6

S: 0 1 2 4 5 6

S: 0 1 3 4 5 6

这样子，我们很容易知道这其实是一个DP的问题

对应的状态转移方程式

if(S[i] == T[j])
	dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else
	dp[i][j] = dp[i-1][j];

AC代码：