简单记录学习~
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: unordered_map<int, TreeNode*> fa; unordered_map<int, bool> vis; void dfs(TreeNode* root){ if(root -> left != nullptr){ fa[root -> left -> val] = root; // 保存该节点的父节点 dfs(root -> left); } if(root -> right != nullptr){ fa[root -> right -> val] = root; dfs(root -> right); } } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { fa[root -> val] = nullptr; dfs(root); while(p!=nullptr){ vis[p -> val] = true; p = fa[p -> val]; // 取该节点的父节点并设置为 true } while(q != nullptr){ if(vis[q -> val]){return q;} q = fa[q -> val]; } return nullptr; } };
