本文主要是介绍深度优先遍历-在二叉树中找到两个节点的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、问题描述
二、解题思路
使用深度递归的方式，如果当前结点val为o1时，返回1，如果当前结点是val为o2时，返回2；
1.当前结点的左右子树结点返回值分别为1和2时，说明该结点是最近的公共祖先结点
2.当前结点值为o1，左或者右子树返回值为2时，说明o1就是公共祖先结点
3.当前结点值为o2，左或者右子树返回值为1时，说明o2就是公共祖先结点
4.注意，当左右子树为空时，返回值为0，这样只要这棵子树里面没有o1或者o2，那么这棵子树就会一直返回0。
import java.util.*;/** public class TreeNode {* int val = 0;* TreeNode left = null;* TreeNode right = null;* public TreeNode(int val) {* this.val = val;* }* }*/public class Solution {int resval=0;/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型*/public int lowestCommonAncestor (TreeNode root, int o1, int o2) {// write code heredfs(root,o1,o2);return resval;}public int dfs(TreeNode root,int target1,int target2){if(root==null){return 0;}else{int leftval=dfs(root.left,target1,target2);int rightval=dfs(root.right,target1,target2);if(root.val==target1){if(leftval==2||rightval==2){//目标值在根节点和左或者右两侧，返回根节点值resval=root.val;return 0;}else{return 1;}}else if(root.val==target2){if(leftval==1||rightval==1){//目标值在根节点和左或者右两侧，返回根节点值resval=root.val;return 0;}else{return 2;}}else{//目标值在根节点左右两侧if(leftval+rightval==3){resval=root.val;return 0;}else{return leftval+rightval;}}}}
}四、刷题链接
在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网
这篇关于深度优先遍历-在二叉树中找到两个节点的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
