题解 | #在二叉树中找到两个节点的最近公共祖先#

import java.util.*;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• } */

public class Solution { /** * * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型 */ //这个题用递归的方法看起来会比较简洁一些，只是逻辑需要静心梳理一下 //核心的思路是找到目标之后层层返回，从最里层返回知道在某一层遇到left和right都不为空的时候，再层层返回此时的root节点， //这个节点被层层返回直到跳出循环,有点绕 public int lowestCommonAncestor(TreeNode root,int o1,int o2){ return helper(root,o1,o2).val; } public TreeNode helper(TreeNode root,int o1,int o2){ if(root == null || root.val == o1 || root.val == o2){ return root; } TreeNode left = helper(root.left,o1,o2); TreeNode right = helper(root.right,o1,o2); if(left == null){ return right; } if(right == null){ return left; } return root; }

}