【Hot100】LeetCode—236. 二叉树的最近公共祖先

本文主要是介绍【Hot100】LeetCode—236. 二叉树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

• 题目连接：236. 二叉树的最近公共祖先

---

1- 思路

递归 + 自底向上

① 自底向上的逻辑的话

• 需要采用后续遍历的方式，最后处理中间结点

② 递归

• 2.1 参数和返回值
  • 返回值为 TreeNode，参数为 root==null || root == p || root == q

• 2.3 遍历逻辑（后续遍历：左右中）

---

2- 实现

⭐236. 二叉树的最近公共祖先——题解思路

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 终止条件if(root == null || root == p || root == q){return root;}// 递归TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);//中if(left==null && right==null){return null;}else if (left!=null && right==null){return left;}else if(left==null && right!=null){return right;}else{return root;}}
}

---

3- ACM 实现

public class commonAncestor {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}public static TreeNode build(String str) {if (str == null || str.length() == 0) {return null;}String input = str.replace("[", "");input = input.replace("]", "");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for (int i = 0; i < parts.length; i++) {if (!parts[i].equals("null")) {nums[i] = Integer.parseInt(parts[i]);} else {nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while (!queue.isEmpty() && index < parts.length) {TreeNode node = queue.poll();if (index < nums.length && nums[index] != null) {node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if (index < nums.length && nums[index] != null) {node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}public static TreeNode findNode(TreeNode root, int val) {if (root == null) {return null;}if (root.val == val) {return root;}TreeNode leftResult = findNode(root.left, val);if (leftResult != null) {return leftResult;}return findNode(root.right, val);}public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 终止条件if(root == null || root == p || root == q){return root;}// 递归TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);//中if(left==null && right==null){return null;}else if (left!=null && right==null){return left;}else if(left==null && right!=null){return right;}else{return root;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);// 读取p和q的值int pVal = sc.nextInt();int qVal = sc.nextInt();TreeNode p = findNode(root,pVal);TreeNode q = findNode(root,qVal);TreeNode res = lowestCommonAncestor(root,p,q);System.out.println("结果是"+res.val);}
}

这篇关于【Hot100】LeetCode—236. 二叉树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---