diff options
Diffstat (limited to 'other/lowest_common_ancestor.cpp')
-rw-r--r-- | other/lowest_common_ancestor.cpp | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/other/lowest_common_ancestor.cpp b/other/lowest_common_ancestor.cpp new file mode 100644 index 0000000..ec99f32 --- /dev/null +++ b/other/lowest_common_ancestor.cpp @@ -0,0 +1,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; + }; +}; |