aboutsummaryrefslogtreecommitdiff
path: root/lowest_common_ancestor.cpp
blob: ec99f32029d9c720e00099478803db07726d459d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "leetcode.h"

class Solution {
public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    frame ans;
    stack<frame> st;
    st.push({root, &ans});
    while (st.size()) {
      frame *top = &st.top(), *parent = top->parent;
      TreeNode *node = top->node;
      if (!node || node == p || node == q) {
        parent->subs.push_back(node);
        st.pop();
      } else if (top->subs.empty()) {
        st.push({node->right, top});
        st.push({node->left, top});
      } else {
        TreeNode *left = top->subs[0], *right = top->subs[1];
        parent->subs.push_back(!left ? right : !right ? left : node);
        st.pop();
      }
    }
    return ans.subs[0];
  }

private:
  struct frame {
    TreeNode *node;
    frame *parent;
    vector<TreeNode *> subs;
  };
};