LeetCode 1644. 二叉樹的最近公共祖先 II

Michael阿明 2021-08-15 22:28:36 阅读数:164

本文一共[544]字,预计阅读时长:1分钟~
leetcode 二叉 最近 公共 祖先

文章目錄

1. 題目

給定一棵二叉樹的根節點 root,返回給定節點 p 和 q 的最近公共祖先(LCA)節點。
如果 p 或 q 之一不存在於該二叉樹中,返回 null。
樹中的每個節點值都是互不相同的。

根據維基百科中對最近公共祖先節點的定義:“兩個節點 p 和 q 在二叉樹 T 中的最近公共祖先節點是後代節點中既包括 p 又包括 q 的最深節點(我們允許一個節點為自身的一個後代節點)”。
一個節點 x 的後代節點是節點 x 到某一葉節點間的路徑中的節點 y。

示例 1:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節點 51 的共同祖先節點是 3

示例 2:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節點 54 的共同祖先節點是 5。根據共同祖先節點的定義,一個節點可以是自身的後代節點。

示例 3:
在這裏插入圖片描述

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
輸出: null
解釋: 節點 10 不存在於樹中,所以返回 null。
提示:
樹中節點個數的範圍是 [1, 104]-109 <= Node.val <= 109
所有節點的值 Node.val 是互不相同的。
p != q

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {

bool findp = false, findq = false;
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

TreeNode* ans = lowestCommonAncestor1(root,p,q);
if(findp && findq)
return ans;
return NULL;
}
TreeNode* lowestCommonAncestor1(TreeNode* root, TreeNode* p, TreeNode* q) {

if(!root) return root;
if(root==p) findp = true;
else if(root==q) findq = true;
auto l = lowestCommonAncestor1(root->left,p,q);
auto r = lowestCommonAncestor1(root->right,p,q);
if(root==p || root==q || (l && r))
return root;
return l ? l : r;
}
};

116 ms 60.3 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753186d.html