【LeetCode】【算法】236. 二叉树最近公共祖先

LeetCode 236. 二叉树最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路

思路：后序遍历（左右中），如果在左/右侧树上找到了该节点则返回对应节点，其公共节点就为中，否则返回null，继续找

代码

/**
 * 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) return root;
        if (root == p || root == q) return root;
        // 递归
        TreeNode treeNodeLeft = lowestCommonAncestor(root.left, p, q);
        TreeNode treeNodeRight = lowestCommonAncestor(root.right, p, q);
        if (treeNodeLeft != null && treeNodeRight != null) return root; // 说明公共节点在root
        else if (treeNodeLeft == null && treeNodeRight != null) return treeNodeRight; // 返回这个节点本身
        else if (treeNodeLeft != null && treeNodeRight == null) return treeNodeLeft;
        else return null; // 没找到p和q，返回null
    }
}