Code & Func

第15天。

并不难的一道题，而且不同寻常的是用栈去做比用递归去做要方便一点。

我这里的想法是，从左向右一直插入就好了，例如输入是[3, 2, 1, 6, 0, 5]

先插入 3 ，然后插入下一个元素时进行讨论：

如果比上一次插入的元素要小，我就直接插入到上一次插入节点的右孩子处就好了。
如果比上一次插入的元素要大，我就用栈回溯到上上次插入节点的位置，进行判断，以此类推。
- 如果在栈中找到了，我就将新元素插入到该节点的右孩子处，并把原来的右子树当成是新元素的左子树。
- 如果没在栈中找到，我就把新元素当成新的根节点，并把原来的数当成新元素的左子树。

代码如下：

1
TreeNode* constructMaximumBinaryTree1(vector<int>& nums) {
2
  if (nums.size() == 0) return nullptr;
3

4
  stack<TreeNode*> st;
5

6
  auto end = nums.end();
7

8
  TreeNode *root = new TreeNode(nums[0]);
9
  TreeNode *p = root;
10

11
  st.push(root);
12

13
  for(auto it = nums.begin() + 1; it != end; ++it) {
14
    int val = *it;
15
    TreeNode *t = new TreeNode(val);
20 collapsed lines
16

17
    if (val < p->val) {
18
      p->right = t;
19
    } else {
20
      while(!st.empty() && val > st.top()->val) st.pop();
21
      if (!st.empty()) {
22
        p = st.top();
23
        t->left = p->right;
24
        p->right = t;
25
      } else {
26
        t->left = root;
27
        root = t;
28
      }
29
    }
30
    p = t;
31
    st.push(p);
32
  }
33

34
  return root;
35
}