#include "leetcode.h" class Solution { public: TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) { frame ans; stack 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 subs; }; };