这道题想了好久没想出来，没想到的是用了递归
分3中情况
1.如果p,q中有一个就是root，那么root就是他们的公共祖先
2.如果root的左子树和右子树，包括了p,q，说明他们的公共祖先是root
3.如果左子树和右子树中有一个为空，那说明p,q只包含在非空的那个子树里
最后面的代码可以简写为：return left?left:right;
题目
code
图解
这道题想了好久没想出来，没想到的是用了递归
分3中情况
1.如果p,q中有一个就是root，那么root就是他们的公共祖先
2.如果root的左子树和右子树，包括了p,q，说明他们的公共祖先是root
3.如果左子树和右子树中有一个为空，那说明p,q只包含在非空的那个子树里
最后面的代码可以简写为：return left?left:right;
题目
code
图解
本文标题：剑指offer- II. 二叉树的最近公共祖先
本文链接：https://www.haomeiwen.com/subject/ccaoihtx.html
网友评论