深度优先遍历-在二叉树中找到两个节点的最近公共祖先

本文主要是介绍深度优先遍历-在二叉树中找到两个节点的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述

二、解题思路

使用深度递归的方式，如果当前结点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;}}}}
}