aboutsummaryrefslogtreecommitdiff
path: root/other/lowest_common_ancestor.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/lowest_common_ancestor.cpp')
-rw-r--r--other/lowest_common_ancestor.cpp33
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;
+ };
+};