菜鸡学习记录
题目链接:236. 二叉树的最近公共祖先 - 力扣(LeetCode) (leetcode-cn.com)
这道题目是使用回溯的方法做的,感觉二叉树一般就是用回溯的方法去做。
找公共祖先,对于某一个节点来说,用lson
和rson
分别表示其左子树和右子树。
思路是先判断其左子树、右子树是否有p
、q
,如果有的话,说明这个节点就是其公共祖先;如果不满足前面这个条件,接下来判断当前节点是否就是p
或q
,如果当前节点是p
,则只要再判断其lson
或rson
中是否有q
;q
也同样做这样的判断。(这边还是看官方的题解才懂的,周末复盘再来一遍)
只要满足上述两个条件中的其中一个,就可以判定节点为公共祖先。
代码
TreeNode res;
Solution() {
res = null;
}
public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
res = root;
}
return lson || rson || root.val == p.val || root.val == q.val;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
boolean find = dfs(root, p, q);
return res;
}