赞
踩
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Input root = [1,2], p = 1, q = 2
Output 1
From: LeetCode
Link: 236. Lowest Common Ancestor of a Binary Tree
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { // If looking at a null node, return null if (root == NULL) return NULL; // If either p or q is the root, then the root is the LCA if (root == p || root == q) return root; // Recursively call the function on the left and right child struct TreeNode* left = lowestCommonAncestor(root->left, p, q); struct TreeNode* right = lowestCommonAncestor(root->right, p, q); // If both left and right are not null, we found our LCA if (left != NULL && right != NULL) return root; // If one of the children returned a node, meaning either p or q was found on left or right subtree. // If neither was found, then this root can't be LCA return left != NULL ? left : right; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。