赞
踩
作者学习算法的教材是LeetCode 101
有需要的同学直接GitHub搜索LeetCode 101即可 **
104. 二叉树的最大深度(难度:简单)
class Solution {
public:
int maxDepth(TreeNode* root) {
return root ? 1 + max(maxDepth(root->left) , maxDepth(root->right)) : 0;
}
};
110. 平衡二叉树(难度:简单)
class Solution { public: bool isBalanced(TreeNode* root) { if (helper(root) != -1){ return true; } else { return false; } } int helper(TreeNode* root) { if (!root) { return 0; } int left = helper(root->left); int right = helper(root->right); if (left == -1 || right == -1 || abs(left - right) > 1) { return -1; } return 1 + max(left , right); } };
543. 二叉树的直径(难度:简单)
class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int count = 0; helper(root , count); return count; } int helper(TreeNode* root , int& count) { if (!root) { return 0; } int left = helper(root->left , count); int right = helper(root->right , count); count = max(left + right , count); return 1 + max(left , right); } };
437. 路径总和Ⅲ(难度:中等)
class Solution { public: int pathSum(TreeNode* root, int sum) { return root ? pathSumStartWithRoot(root , sum) + pathSum(root->left , sum) + pathSum(root->right , sum) : 0; } int pathSumStartWithRoot(TreeNode* root , int sum) { if (!root) { return 0; } int count = root->val == sum ? 1 : 0; count += pathSumStartWithRoot(root->left , sum - root->val); count += pathSumStartWithRoot(root->right , sum - root->val); return count; } };
101.对称二叉树(难度:简单)
class Solution { public: bool isSymmetric(TreeNode* root) { return !root ? true : isSymmetric(root->left , root->right); } bool isSymmetric(TreeNode* left , TreeNode* right) { if (!left && !right) { return true; } if (!left || !right) { return false; } if (left->val != right->val) { return false; } return isSymmetric(left->left , right->right) && isSymmetric(left->right , right->left); } };
1110. 删点成林(难度:中等)
class Solution { public: vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) { set<int> dict(to_delete.begin() , to_delete.end());//以空间换时间 vector<TreeNode*> forest; root = helper(root , dict , forest); if (root) { forest.push_back(root); } return forest; } TreeNode* helper(TreeNode* root , set<int> &dict , vector<TreeNode*> &forest) { if (!root) { return root; } root->left = helper(root->left , dict , forest); root->right = helper(root->right , dict , forest); if (dict.count(root->val)) { if (root->left) { forest.push_back(root->left); } if (root->right) { forest.push_back(root->right); } root = nullptr; } return root; } };
637. 二叉树的层平均值(难度:简单)
class Solution { public: vector<double> averageOfLevels(TreeNode* root) { queue<TreeNode*> q; vector<double> result; if (!root) { return result; } q.push(root); while (!q.empty()) { int count = q.size(); double sum = 0; for (int i = 0 ; i < count ; i++) { sum += q.front()->val; if (q.front()->left) { q.push(q.front()->left); } if (q.front()->right) { q.push(q.front()->right); } q.pop(); } result.push_back(sum/count); } return result; } };
102. 二叉树的层次遍历(难度:中等)
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if(!root) { return vector<vector<int>>(); } vector<vector<int>> result; vector<int> res; queue<TreeNode*> q; q.push(root); while(!q.empty()) { int count = q.size();//q.size()的值会变化 for(int i = 0 ; i < count ; i++) { TreeNode* temp = q.front(); res.push_back(temp->val); q.pop(); if(temp->left != nullptr) { q.push(temp->left); } if(temp->right != nullptr) { q.push(temp->right); } } result.push_back(res); res.clear(); } return result; } };
105. 从前序与中序遍历序列构造二叉树(难度:中等)
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { unordered_map<int , int> hash; if (preorder.empty()) { return nullptr; } for (int i = 0 ; i < preorder.size() ; i++) { hash[inorder[i]] = i; } return helper(preorder , hash , 0 , preorder.size() - 1 , 0); } TreeNode* helper(vector<int>& preorder , unordered_map<int , int>& hash , int s0 , int e0 , int s1) { if (s0 > e0) { return nullptr; } int mid = preorder[s1] , index = hash[mid] , leftLen = index - s0; TreeNode* node = new TreeNode(mid); node->left = helper(preorder , hash , s0 , index - 1 , s1 + 1); node->right = helper(preorder , hash , index + 1 , e0 , s1 + leftLen + 1); return node; } };
144. 二叉树的前序遍历(难度:中等)
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; if (!root) { return result; } stack<TreeNode*> s; s.push(root); while(!s.empty()) { TreeNode* node = s.top(); s.pop(); result.push_back(node->val); if(node->right) { s.push(node->right); } if(node->left) { s.push(node->left); } } return result; } };
左子树中所有节点的值小于父节点,右子树中所有节点的值大于父节点;
对于一个二叉查找树,可以在O(nlogn)的时间内查找一个值是否存在:从根节点开始,若当前节点的值大于查找值,则向左下走,反之向右下走;
二叉查找树是有序的,中序遍历的结果是排序好的数组。
一个二叉查找树的实现代码如下:
template <class T>
class BST {
struct Node {
T data;
Node* left;
Node* right;
};
}
Node* makeEmpty(Node* t) {
if (t == nullptr) {
return nullptr;
}
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
return nullptr;
}
Node* insert(Node* t , T x) {
if (t == nullptr) {
t = new Node;
t->data = x;
t->left = nullptr;
t->right = nullptr;
}
else if (x > t->data) {
t->right = insert(t->right , x);
}
else if (x < t->data) {
t->left = insert(r->left , x);
}
return t;
}
Node* find(Node* t , T x) {
if (t == nullptr) {
return nullptr;
}
else if (x > t->data) {
return find(t->right , x);
}
else if (x < t->data) {
return find(t->left , x);
}
return t;
}
Node* findMin(Node* t) {
if (t == nullptr || t->left == nullptr) {
return t;
}
return findMin(t->left);
}
Node* findMax(Node* t) {
if (t == nullptr || t->right == nullptr) {
return t;
}
return findMin(t->right);
}
Node* remove(Node* t , T x) { Node* temp; if (t == nullptr) { return nullptr; } else if (x < t->data) { t->left = remove(t->left , x); } else if (x > t->data) { r->right = remove(t->right , x); } else if (t->left && t->right) { temp = findMin(t->right); t->data = temp->data; t->right = remove(t->right , t->data); } else { temp = t; if (t->left == nullptr) { t = t->tight; } else if (t->right == nullptr) { t = t->left; } delete temp; } return t; }
99. 恢复二叉搜索树(难度:困难)(待进阶)
class Solution { public: void recoverTree(TreeNode* root) { vector<int> pre_result , ino_result , check_result; pre_result = preorder(root , pre_result); ino_result = inorder(root , ino_result); check_result = check(ino_result); for(int i = 0 ; i < pre_result.size() ; i++) { if (pre_result[i] == check_result[0]) { pre_result[i] = check_result[1]; } else if (pre_result[i] == check_result[1]) { pre_result[i] = check_result[0]; } } root = makeEmpty(root); //root = new TreeNode; root->val = pre_result[0]; root->left = nullptr; root->right = nullptr; for (int i = 1 ; i < pre_result.size() ; i++) { root = insert(root , pre_result[i]); } } vector<int> preorder(TreeNode* root , vector<int>& pre_result) { if (root == nullptr) { return pre_result; } pre_result.push_back(root->val); preorder(root->left , pre_result); preorder(root->right , pre_result); return pre_result; } vector<int> inorder(TreeNode* root , vector<int>& ino_result) { if (root == nullptr) { return ino_result; } inorder(root->left , ino_result); ino_result.push_back(root->val); inorder(root->right , ino_result); return ino_result; } vector<int> check(vector<int> ino_result) { vector<int> check_result; int flag = 0 , temp = 0; for(int i = 0 ; i < ino_result.size() - 1 ; i++) {//-1防止数组越界 if (flag == 0 && ino_result[i] > ino_result[i + 1]) { flag = 1; check_result.push_back(ino_result[i]); temp = ino_result[i + 1]; } else if (flag == 1 && ino_result[i] > ino_result[i + 1]) { flag = -1; check_result.push_back(ino_result[i + 1]); } } if (flag == 1) { check_result.push_back(temp); } return check_result; } TreeNode* makeEmpty(TreeNode* root) { if(root->left != nullptr) { delete root->left; } if(root->right != nullptr) { delete root->right; } return root; } TreeNode* insert(TreeNode* root , int x) { if (root == nullptr) { root = new TreeNode; root->val = x; root->left = nullptr; root->right = nullptr; } if (x > root->val) { root->right = insert(root->right , x); } else if (x < root->val) { root->left = insert(root->left , x); } return root; } };
669. 修剪二叉搜索树(难度:中等)
class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(!root) { return root; } if(root->val < low) { return trimBST(root->right , low , high);//右子树可能在范围内 } if (root->val > high) { return trimBST(root->left , low , high);//左子树可能在范围内 } root->left = trimBST(root->left , low , high);//检查并构造左子树 root->right = trimBST(root->right , low , high);//检查并构造右子树 return root; } };
208.实现Tire(前缀树)(难度:中等)
226. 翻转二叉树(难度:简单)
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) {//处理空树
return root;
}
swap(root->left , root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
617. 合并二叉树(难度:简单)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。