LeetCode Beautiful Arrangement Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the i_th position (1 ≤ i ≤ N) in this array:

1. The number at the i_th position is divisible by i.
2. i is divisible by the number at the i_th position.

Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

1. N is a positive integer and will not exceed 15.

1. A[i]能整除i
2. i能整除A[i]

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

根据树的先序遍历和中序遍历结果，重构这棵树。 其实大学的时候就有这样的作业，如果在纸上做，还是很简单的，但要实现成代码，稍微有点难理清这里的关系。 我们先来看一个纸上的解题过程，假设有下面这样一棵树：

        3
     /     \
    9       20
  /  \     /   \
 1    2  15    17

• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

首先我们可以根据先序遍历结果找到根节点3，然后在中序遍历中看看3所处的位置，那么3左边的就是左孩子节点，右边的就是右孩子节点。我们在中序遍历中看看3左边有3个节点，说明3的左子树共有3个节点，同理右子树有3个节点。所以我们在先序遍历中也能知道3后面的3个节点是左子树，再后面3个节点是右子树，这样就把两个遍历结果分成了两部分：

• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

在红色部分递归就是3的左子树，在蓝色部分递归就是3的右子树。 纸上解题好说，但是代码实现，我开始还把自己搞糊涂了，代码很复杂，后来参考了这位大神的博客，代码好简洁易懂，赞一个：

class Solution {
private:
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash)
    {
        if (preL > preR || inL > inR)
            return NULL;
        TreeNode* root = new TreeNode(preorder[preL]);
        size_t idx = hash[root->val];
        root->left = dfs(preorder, inorder, preL + 1, idx – inL + preL, inL, idx – 1, hash);
        root->right = dfs(preorder, inorder, idx – inL + preL + 1, preR, idx + 1, inR, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        if (preorder.size() == 0)
            return NULL;
        unordered_map<int, size_t> hash;
        for (size_t i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, preorder.size() – 1, 0, inorder.size() – 1, hash);
    }
};

本代码提交AC，用时16MS。
代码中有两点需要注意的，一是为了在中序遍历中快速找到根节点，提前对中序遍历结果hash了，因为题目中说了不会有重复元素；二是在dfs递归的时候，要算好下标的起止位置，一定不要弄错了，特别是preorder在左右子树中的起止位置。

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

给定一个字符面板和一个单词，问能否在该面板中搜索到该单词，搜索路径只能水平或垂直。 简单的深度搜索题，首先找到第一个字符的起始位置，然后深度往该字符的上下左右搜，只要有一个true就返回true，否则重置标记位，返回false。 完整代码如下：

class Solution {
private:
    bool dfs(vector<vector<char> >& board, vector<vector<char> >& mark, int row, int col, string& word, int step)
    {
        if (board[row][col] != word[step])
            return false;
        if (step == word.size() – 1)
            return true;
        mark[row][col] = 1;
        if (row – 1 >= 0 && mark[row – 1][col] == 0) {
            bool ans = dfs(board, mark, row – 1, col, word, step + 1);
            if (ans)
                return true;
        }
        if (row + 1 < board.size() && mark[row + 1][col] == 0) {
            bool ans = dfs(board, mark, row + 1, col, word, step + 1);
            if (ans)
                return true;
        }
        if (col – 1 >= 0 && mark[row][col – 1] == 0) {
            bool ans = dfs(board, mark, row, col – 1, word, step + 1);
            if (ans)
                return true;
        }
        if (col + 1 < board[0].size() && mark[row][col + 1] == 0) {
            bool ans = dfs(board, mark, row, col + 1, word, step + 1);
            if (ans)
                return true;
        }
        mark[row][col] = 0;
        return false;
    }
public:
    bool exist(vector<vector<char> >& board, string word)
    {
        if (word.size() == 0)
            return true;
        int m = board.size();
        if (m == 0)
            return false;
        int n = board[0].size();
        if (n == 0)
            return false;
        vector<vector<char> > mark(m, vector<char>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word[0] && dfs(board, mark, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }
};

本代码提交AC，用时9MS，击败95.63%的人。

114. Flatten Binary Tree to Linked List

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

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

把一棵二叉树展开成一个链表，链表还是借助树的数据结构，只不过是借用了树的右孩子指针作为链表的指针。 仔细观察发现新的链表的顺序和树的先序遍历的顺序一致，如果能使用额外的空间，则先序遍历后把节点存到数组中，然后依次链接起来。 如果不使用额外空间，则只能想办法在DFS时就建立好链接关系。先序遍历的顺序是根左右，但是这题为了方便，我们先对右孩子建立链表，然后把右孩子接到父亲的左孩子的最右下角的节点上。比如上图中，我们建立好5->6的链表之后，需要把它接到4号节点的右边。

         1
        /
       2
      / \
     3   4
          \
           5
            \
             6

所以针对右孩子，我们需要根据父节点找到父节点的左子树的最右下角的节点。但是针对左孩子时，因为此时右孩子已经建立好链表并且接到了左孩子正确的位置上，所以只需要把左孩子接到父亲的右孩子位置，并把原来的左孩子置空，下图就是把上图1的左子树放到了右边，左边置为空。

   1
     \
       2
      / \
     3   4
          \
           5
            \
             6

完整代码如下：

class Solution2 {
public:
    void dfs(TreeNode* par, TreeNode* cur)
    {
        if (cur == NULL)
            return;
        if (par) {
            if (cur == par->right) {
                if (par->left) {
                    TreeNode* tmp = par->left;
                    while (tmp->right)
                        tmp = tmp->right;
                    tmp->right = cur;
                    par->right = NULL;
                }
            }
            else {
                par->right = cur;
                par->left = NULL;
            }
        }
        if (cur->right)
            dfs(cur, cur->right);
        if (cur->left)
            dfs(cur, cur->left);
    }
    void flatten(TreeNode* root) { dfs(NULL, root); }
};

本代码提交AC，用时6MS。
还有一种思路比这简单，上面的解法需要while循环查找左兄弟的最右下角的节点，如果我们在DFS中直接返回尾节点，就不需要while查找了。
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：
1
/    \
2     5
\       \
3      6 <- rightTail
\
4  <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
代码如下：

class Solution {
public:
    TreeNode* dfs(TreeNode* root)
    {
        if (!root)
            return NULL;
        TreeNode* leftTail = dfs(root->left);
        TreeNode* rightTail = dfs(root->right);
        if (root->left) {
            leftTail->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }
        if (rightTail)
            return rightTail;
        if (leftTail)
            return leftTail;
        return root;
    }
    void flatten(TreeNode* root) { dfs(root); }
};

本代码提交AC，用时6MS。