面试题36. 二叉搜索树与双向链表 面试题37. 序列化二叉树

 面试题36. 二叉搜索树与双向链表

递归实现

问题：栈溢出：  

[28,-98,67,null,-89,62,null,-97,-25,null,64,null,null,-72,-9,null,null,-88,-41,null,-7,null,-78,-53,null,null,2,-85,-77,-69,-42,-1]

class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}
};/*
全局保存头尾指针
先递归左子树
连接，并更新尾部指针
再递归右子树
*/Node*head = nullptr, *tail = nullptr;void inOrder(Node*& root) {if (root == nullptr) {return;}inOrder(root->left);if (head == nullptr) {head = root;}if (tail != nullptr) {tail->right = root;root->left = tail;}tail = root;inOrder(root->right);}Node* treeToDoublyList(Node* root) {if (root == nullptr) {return nullptr;}inOrder(root);if (tail&&head) {tail->right = head;head->left = tail;}return head;}Node* buildBST(Node*t,int num) {if (t == nullptr) {t = new Node(num);}else{if (num < t->val) {t->left = buildBST(t->left, num);}else{t->right = buildBST(t->right,num);}}return t;
}Node* creat() {Node* t = nullptr;int n;cin >> n;while (n--){int num;cin >> num;t=buildBST(t, num);}return t;}int main()
{Node* root=creat();treeToDoublyList(root);std::cout << "Hello World!\n";
}

 栈

• 将树的左子树依次存入stack
• 每次pop出一个Node将其右子树的左子树也依次存入stack
• 饭后做连接操作

Node* treeToDoublyList(Node* root) {if (root == nullptr) {return nullptr;}Node*cur = root;Node*before = nullptr;Node*after = nullptr;Node*head = nullptr;stack<Node*> stac;while (cur){stac.push(cur);head = cur;cur = cur->left;}while (!stac.empty()) {cur = stac.top();stac.pop();Node*tmp = cur->right;while (tmp) {stac.push(tmp);tmp = tmp->left;}if (stac.empty()) {after = head;}else{after = stac.top();}cur->left = before;cur->right = after;before = cur;}head->left = before;return head;}

 面试题37. 序列化二叉树

递归

void preOrder(TreeNode* root, string&res) {if (root) {res += "#,";return;}res += to_string(root->val) + ",";preOrder(root->left,res);preOrder(root->right,res);
}// Encodes a tree to a single string.
string serialize(TreeNode* root) {string res="";if (root == nullptr) {return res;}preOrder(root,res);return res;
}
TreeNode* preOrderDecode(int& p, const string& data) {if (data[p] == '#') {p += 2;return nullptr;}bool is_n = false;if (data[p] == '-') {is_n = true;p++;}int num = 0;while (data[p]!=','){num = num * 10 + (data[p] - '0');p++;}if (is_n) num = -num;auto root = new TreeNode(num);root->left = preOrderDecode(p, data);root->right = preOrderDecode(p, data);return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {if (data.size() <= 0) {return nullptr;}int p = 0;return preOrderDecode(p,data);}
};

迭代 层次