leetcode 236 而哈数的最近公共祖先
leetcode 236 而哈数的最近公共祖先
简介
dfs 找出路劲,然后长链在短链里面找.
code
/**
* 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: int level = 0; vector<TreeNode*> path1; vector<TreeNode*> path2; bool dfs(TreeNode *n, vector<TreeNode*> &path, TreeNode *p){ if(n == p){
path.push_back(n); return true;
} if(n->left){ if(dfs(n->left, path, p)){
path.push_back(n); return true;
}
} if(n->right){ if(dfs(n->right, path, p)){
path.push_back(n); return true;
}
} return false;
} TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, path1, p);
dfs(root, path2, q); // 长链在短链找
if(path1.size() >= path2.size()){ int i=0; while(i<path1.size()){ if(find(path2.begin(), path2.end(), path1[i])!= path2.end()){ return path1[i];
}
i++;
}
} else{ int i= 0; while(i<path2.size()){ if(find(path1.begin(), path1.end(), path2[i])!= path1.end()){ return path2[i];
}
i++;
}
} return nullptr;
}
};class Solution { private TreeNode ans; public Solution() { // 使用公共变量记得在构造函数中初始化
this.ans = null;
} private boolean dfs(TreeNode root, TreeNode p, TreeNode q){ if(root == null) return false;
bool lson = dfs(root.left, p, q);
bool rson = dfs(root.right, p, q); if((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
} return lson || rson || (root.val == p.val || root.val == q.val));
} public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { this.dfs(root, p, q); return this.ans;
}
}Hope is a good thing,maybe the best of things,and no good thing ever dies.----------- Andy Dufresne