# LeetCode DFS(中)

4 分钟读完

DFS Medium级别题目有10道，本篇解题如下：

#1.Path Sum II ref
PathSum题解

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

``````            5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1
return
[
[5,4,11,2],
[5,8,4,5]
]
``````

#2.Sum Root to Leaf Numbers ref

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.

For example,

``````  1
/ \
2   3   The root-to-leaf path 1->2 represents the number 12.     The root-to-leaf path 1->3 represents the number 13.     Return the sum = 12 + 13 = 25.
``````

#3.Flatten Binary Tree to Linked List ref

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

``````       1
/ \
2   5
/ \   \
3   4   6
``````

The flattened tree should look like:

`````` 1
\
2
\
3
\
4
\
5
\
6
``````

#4.Validate Binary Search Tree ref

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 right subtrees must also be binary search trees.

#5.Populating Next Right Pointers in Each Node ref

Given a binary tree
}
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).
For example,
Given the following perfect binary tree,

``````       1
/  \
2    3
/ \  / \
4  5  6  7
``````

After calling your function, the tree should look like:

``````       1 -> NULL
/  \
2 -> 3 -> NULL
/ \  / \
4->5->6->7 -> NULL
``````

###1.思路一 层次遍历二叉树，入队列时，对每一个节点标记上层级；出队列时，按层级保存到一个二维数组中；最后按层级连接前后结点next指针。

###2.思路二 还是层次遍历的思想，用两个数组模拟队列，队列q中的数据始终是同一层级的结点，qt作为临时缓冲队列。

###3.思路三 该题是DFS系列的题目哎，而思路一和二明明都是BFS的解法啊。 