|
一、
题目:
236. Lowest Common Ancestor of a Binary Tree
DescriptionHintsSubmissionsDiscussSolution
Pick One
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).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.
Example 2:
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.
Note:
- All of the nodes' values will be unique.
- p and q are different and both values will exist in the binary tree.
解答：
/**
* 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 {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//递归法，根据root某一侧子树能不能找到p或者q 来判断
if(!root || root == p || root == q)//若是root为空，或者等于左右中一个，返回
return root;
TreeNode* lc = lowestCommonAncestor(root->left, p, q);//在root->left左子树找p,q 若找到，返回二者中任意一个
TreeNode* rc = lowestCommonAncestor(root->right, p, q);
if(lc && rc)//若是root两侧子树都找到了p，q二者之一，则root 就是lca
return root;
if(!lc)//若果左边子树lc没有找到二者之一，那么rc是lca
return rc;
if(!rc)//若果右边子树rc没又找到二者之一，则lc是lca
return lc;
}
};
二、
题目：
110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
解答：
/**
* 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 {
public:
bool isBalanced(TreeNode* root) {
if(!root)
return Flag;
depthOfTree(root);
return Flag;
}
//开始时候，求深度和判断语句分别进行了两次递归，这样可以进行一次递归就可以
int depthOfTree(TreeNode* root)
{
if(!root)
return 0;
int leftDepth = depthOfTree(root->left);
int rightDepth = depthOfTree(root->right);
//多加的一部分判断，合二次递归为一
if(abs(leftDepth - rightDepth) > 1)
{
Flag = false;
}
return 1 + max(leftDepth, rightDepth);
}
private:
bool Flag = true;
};
| 
转播
