leetcode

0 class Solution {

1 public:

2 TreeNode *lcaDeepestLeaves(TreeNode *root) {

3 int8_t height[1001] = {0};

4 stack<TreeNode *> s({root});

5

6 TreeNode *res;

7 int maxi = INT_MIN;

8 while (!s.empty()) {

9 TreeNode *root = s.top();

10 if (root->val >= 0) {

11 if (root->left) {

12 height[root->left->val] = height[root->val] + 1;

13 s.push(root->left);

14 }

15 if (root->right) {

16 height[root->right->val] = height[root->val] + 1;

17 s.push(root->right);

18 }

19 root->val = -root->val - 1;

20 continue;

21 }

22 s.pop();

23 root->val = -(root->val + 1);

24

25 if (!root->left && !root->right) {

26 if (height[root->val] > maxi) {

27 maxi = height[root->val];

28 res = root;

29 }

30 continue;

31 }

32

33 int8_t l = 0, r = 0;

34 if (root->left) l = height[root->left->val];

35 if (root->right) r = height[root->right->val];

36

37 if (l || r) height[root->val] = max(l, r);

38 if (height[root->val] >= maxi && l == r) {

39 maxi = height[root->val];

40 res = root;

41 }

42 }

43 return res;

44 }

45 };