后序遍歷: 先左爽航，再右丘薛，最后是根節(jié)點(diǎn)沉删。
這類題目的模板：
- 遞歸終止娱挨，返回0
- 遞歸求left深度
- 遞歸求right深度
- 對(duì)left和right進(jìn)行比較余指，
- 返回root結(jié)果
145. 二叉樹的后序遍歷
給定一個(gè)二叉樹，返回它的 后序 遍歷跷坝。
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. 完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)
給出一個(gè)完全二叉樹酵镜，求出該樹的節(jié)點(diǎn)個(gè)數(shù)。
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. 二叉樹的最大深度
給定一個(gè)二叉樹柴钻，找出其最大深度淮韭。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
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. 二叉樹的最小深度
給定一個(gè)二叉樹贴届，找出其最小深度靠粪。最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量蜡吧。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
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. 平衡二叉樹
給定一個(gè)二叉樹，判斷它是否是高度平衡的二叉樹占键。
注意: 這里的高度平衡二叉樹指的是一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過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. 二叉樹的直徑
給定一棵二叉樹，你需要計(jì)算它的直徑長(zhǎng)度捞慌。一棵二叉樹的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值耀鸦。這條路徑可能穿過根結(jié)點(diǎn)。
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. 最長(zhǎng)同值路徑
給定一個(gè)二叉樹啸澡，找到最長(zhǎng)的路徑袖订，這個(gè)路徑中的每個(gè)節(jié)點(diǎn)具有相同值。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)嗅虏。
注意：兩個(gè)節(jié)點(diǎn)之間的路徑長(zhǎng)度由它們之間的邊數(shù)表示洛姑。
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;
}
};
