Lowest Common Ancestor of a Binary Tree

做到这个题才发现之前做的关于二叉检索树的写复杂了，，其实可以直接根据二叉检索树的特点进行判断（从树根开始，某一节点的值大于待搜的两个节点则在左边找，小于待搜的两个节点则在右边找，否则返回该节点即可）。这道题倒是必须用DFS来解决。

class Solution {public://DFS代码void findNode(TreeNode* root, TreeNode* toFind, vector<TreeNode*> &curPath, bool& find){if(root == toFind){curPath.push_back(root);find = true;return;}if(root == nullptr)return;curPath.push_back(root);if(root -> left != nullptr){findNode(root -> left, toFind, curPath, find);if(find == true)return;curPath.pop_back();}if(root -> right != nullptr){findNode(root -> right, toFind, curPath, find);if(find == true)return;curPath.pop_back();}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//路径放在两个vector中vector<TreeNode*> pPath, qPath;TreeNode* result;bool pFind = false, qFind = false;//查找两个路径findNode(root, p, pPath, pFind);findNode(root, q, qPath, qFind);if(qFind == false || pFind == false)return nullptr;//从得到的路径查找公共祖先for(int index = 0; index < pPath.size() && index < qPath.size() && qPath[index] == pPath[index]; index++){result = pPath[index];}return result;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

看不见我将要去的地方，记不得我已经去过的地方。