leetcode

0 class Solution {

1 public:

2 TreeNode *trimBST(TreeNode *root, int low, int high) {

3 if (!root) return nullptr;

4 while (root) {

5 if (root->val < low)

6 root = root->right;

7 else if (root->val > high)

8 root = root->left;

9 else

10 break;

11 }

12 stack<pair<TreeNode *, TreeNode **>> st;

13 TreeNode *head = root, **link = nullptr;

14 while (true) {

15 while (root) {

16 if (root->val < low)

17 root = *link = root->right;

18 else if (root->val > high)

19 root = *link = root->left;

20 else {

21 if (root->right) st.push({root->right, &root->right});

22 link = &root->left;

23 root = root->left;

24 }

25 }

26 if (st.empty()) break;

27 root = st.top().first;

28 link = st.top().second;

29 st.pop();

30 }

31 return head;

32 }

33 };