【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)!