自学内容网 自学内容网

【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
    }
}

原文地址:https://blog.csdn.net/passer__jw767/article/details/143530513

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!