平衡二叉树
[https://programmercarl.com/0110.平衡二叉树.html#算法公开课]
解法
使用了自顶向下递归，会重复调用find_deepth，时间复杂度较高。还有一种时间复杂度更低的自底向上递归。
class Solution {
public:bool isBalanced(TreeNode* root) {bool res;if(!root) return true;if(find_deepth(root->right) - find_deepth(root->left) > 1 || find_deepth(root->right) - find_deepth(root->left) < -1) return false;return isBalanced(root->left) & isBalanced(root->right);}int find_deepth(TreeNode* root){if(!root) return 0;return max(find_deepth(root->left),find_deepth(root->right)) + 1;}
};
自底向上递归
class Solution {
public:int height(TreeNode* root) {if (root == NULL) {return 0;}int leftHeight = height(root->left);int rightHeight = height(root->right);if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {return -1;} else {return max(leftHeight, rightHeight) + 1;}}bool isBalanced(TreeNode* root) {return height(root) >= 0;}
};
二叉树的所有路径
[https://programmercarl.com/0257.二叉树的所有路径.html#算法公开课]
解法
class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;string path = "";find_leaf(root,path,res);return res;}void find_leaf(TreeNode* root,string path,vector<string> &res){if (root->right || root->left){path += to_string(root->val);path += "->";if(root->right) find_leaf(root->right,path,res);if(root->left) find_leaf(root->left,path,res);}else{path += to_string(root->val);res.push_back(path);return;}}
};
左叶子之和
[https://programmercarl.com/0404.左叶子之和.html]
解法
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(!root) return 0;if(!root->right && !root->left) return 0;return find(root->right,0) + find(root->left,1);}int find(TreeNode* root,int sign){if(!root) return 0;if(!root->right && !root->left && sign == 1) return root->val;return find(root->left,1) + find(root->right,0);}
};
完全二叉树的节点个数
[https://programmercarl.com/0222.完全二叉树的节点个数.html#算法公开课]
解法
迭代的层序遍历，记录节点个数
class Solution {
public:int countNodes(TreeNode* root) {if(!root) return 0;queue<TreeNode*> que;que.push(root);int count = 0;while(!que.empty()){root = que.front();que.pop();count++;if(root->right) que.push(root->right);if(root->left) que.push(root->left);}return count;}
};