后序遍历: 先左，再右，最后是根节点。
这类题目的模板：
- 递归终止，返回0
- 递归求left深度
- 递归求right深度
- 对left和right进行比较，
- 返回root结果
145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
class Solution {
private:
vector<int> ans;
public:
vector<int> postorderTraversal(TreeNode* root) {
postOrder(root);
return ans;
}
void postOrder(TreeNode* root){
if (root == NULL) return ;
postOrder(root->left);
postOrder(root->right);
ans.push_back(root->val);
return;
}
};
222. 完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL ) return 0;
int left = countNodes(root->left);
int right= countNodes(root->right);
return left + right + 1;
}
};
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return left > right ? left + 1 : right + 1;
}
};
110. 二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点
class Solution {
public:
int minDepth(TreeNode* root) {
if ( root == NULL ){
return 0;
}
int left = minDepth(root->left);
int right = minDepth(root->right);
if ( root->left == NULL || root->right == NULL){
return left == 0 ? right + 1 : left + 1;
} else{
return left > right ? right + 1 : left + 1;
}
}
};
110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
注意: 这里的高度平衡二叉树指的是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
class Solution {
private:
bool status;
public:
bool isBalanced(TreeNode* root) {
status = true;
depth(root);
return status;
}
int depth(TreeNode* root){
if ( root == NULL) return 0;
int left = depth(root->left) ;
int right = depth(root->right) ;
if ( abs(left-right) > 1) status=false;
return left > right ? left + 1 : right + 1;
}
};
543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
class Solution {
int ans;
public:
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
int depth(TreeNode* root){
if (root == NULL) return 0;
int left = depth(root->left);
int rigth = depth(root->right);
ans = left + right + 1 > ans ? left + right + 1 : ans;
return left > right ? left + 1 : right + 1;
}
};
687. 最长同值路径
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
class Solution {
private:
int ans;
public:
int longestUnivaluePath(TreeNode* root) {
if ( root == NULL) return 0;
depth(root);
return ans;
}
int depth(TreeNode* root){
if (root == NULL) return 0;
int left = depth(root->left);
int right = depth(root->right);
int arrowLeft = 0, arrowRight = 0;
if ( root->left != NULL && root->val == root->left->val){
arrowLeft += left + 1;
}
if ( root->right != NULL && root->val == root->right->val){
arrowRight += right + 1;
}
ans = (arrowLeft + arrowRight ) > ans ? (arrowLeft + arrowRight ) : ans;
return arrowLeft > arrowRight ? arrowLeft : arrowRight;
}
};
