题目链接 LeetCode 236
我遇到了的问题:在findpath这个函数中使用了dfs来找到两个节点之间的路径。但是个人觉得这种写法很不简洁(或者不是常用的写法),特别是引入了found这个变量,以及连续几个if (!found)判断语句。请问是否能对代码进行改进?
代码:
/**
* 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:
bool found = false;
vector<TreeNode*> path;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> p_to_root;
vector<TreeNode*> q_to_root;
findpath(root, p, p_to_root);
found = false;
findpath(root, q, q_to_root);
int i = 0;
int len = min(p_to_root.size(), q_to_root.size());
while (p_to_root[i] == q_to_root[i] && i < len)
i++;
return p_to_root[i-1];
}
void findpath(TreeNode* root, TreeNode* p, vector<TreeNode*> &path){
if (root != p){
if (!root){
path.push_back(root);
return;
}
if (!found) path.push_back(root);
if (!found) findpath(root->left, p, path);
if (!found) path.pop_back();
if (!found) findpath(root->right, p, path);
if (!found) path.pop_back();
return;
}
else {
path.push_back(root);
found = true;
return;
}
}
};
这么写可以AC,但是希望可以改进写法,使得更加好看。谢谢!
代码优化