---
title: leetcode 1028
tags: leetcode, tree
---

// https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *root;
    void addNode(int num, int depth) {
      TreeNode *now = root;
      TreeNode *newNode = new TreeNode(num);
      if (depth == 0) {
        root = newNode;
        return;
      }
      for (int i=0; i<depth-1; i++) {
        if (now -> right) now = now -> right;
        else  now = now -> left;
      }
      if (now -> left) {
        now -> right = newNode;
      } else {
        now -> left = newNode;
      }
    }
public:
    TreeNode* recoverFromPreorder(string S) {
      int depth = 0;
      for (int i=0; i<S.length(); i++) {
        if (S[i] == '-') depth ++;
        else if (S[i] >= '0' && S[i] <= '9') {
          int num = 0;
          do {
            num = num * 10 + S[i] - '0';
            i++;
          } while (i < S.length() && S[i] >= '0' && S[i] <= '9');
          i--;
          addNode(num, depth);
          depth = 0;
        }
      }
      return root;
    }
};