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