HOT100(二叉树)

二叉树

二叉树的中序遍历

class Solution {
public:void traversal(TreeNode* root, vector<int> & vec){if(root == nullptr) return;traversal(root->left, vec);vec.push_back(root->val);traversal(root->right, vec);}vector<int> inorderTraversal(TreeNode* root) {vector<int> vec;traversal(root, vec);return vec;}
};

二叉树的最大深度

class Solution {
public:int getdepth(TreeNode* root){if(root == nullptr) return 0;int rightdepth = getdepth(root->right);int leftdepth = getdepth(root->left);return max(rightdepth, leftdepth)+1;}int maxDepth(TreeNode* root) {return getdepth(root);}
};

226翻转二叉树

class Solution {
public:void change_Tree(TreeNode* cur){if(cur == NULL) return;TreeNode* pre = cur->left;cur->left = cur->right;cur->right = pre;change_Tree(cur->left);change_Tree(cur->right);}TreeNode* invertTree(TreeNode* root) {change_Tree(root);return root;}
};

对称二叉树

class Solution {
public:bool traversal(TreeNode* Tleft, TreeNode* Tright){if(Tleft == NULL && Tright == NULL) return true;if(Tleft == NULL|| Tright == NULL) return false;if(Tleft->val != Tright->val) return false;bool outTree = traversal(Tleft->left,Tright->right);bool inTree = traversal(Tleft->right, Tright->left);return outTree && inTree;}bool isSymmetric(TreeNode* root) {return traversal(root->left,root->right);}
};

二叉树的直径

class Solution {int ans;int depth(TreeNode* rt) {if(rt == NULL) return 0;int L = depth(rt->left);int R = depth(rt->right);ans = max(ans, L+R+1);return max(L, R)+1;}
public:int diameterOfBinaryTree(TreeNode* root) {ans = 0;depth(root);return ans-1;}
};

二叉树的层序遍历

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if(root != NULL) que.push(root);vector<vector<int>> result;while(!que.empty()) {int size = que.size();vector<int> vec;for(int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

108. 将有序数组转换为二叉搜索树``

class Solution {
public:TreeNode* traversal(vector<int>& nums, int left, int right) {if(left > right) return NULL;int mid = left + (right - left) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums, left, mid - 1);root->right = traversal(nums, mid + 1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums, 0, nums.size() - 1);}
};

98.验证二叉搜索树

class Solution {
public:long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);// 中序遍历，验证遍历的元素是不是从小到大if (maxVal < root->val) maxVal = root->val;else return false;bool right = isValidBST(root->right);return left && right;}
};
//迭代法
class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL; // 记录前一个节点while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->left;                // 左} else {cur = st.top();                 // 中st.pop();if (pre != NULL && cur->val <= pre->val)return false;pre = cur; //保存前一个访问的结点cur = cur->right;               // 右}}return true;}
};

二叉搜索树中第k小元素

中序遍历二叉树，vector容器装，输出num[k-1];

class Solution {
public:vector<int> nums;void travelsal(TreeNode* cur) {if(cur == nullptr) return;travelsal(cur->left);nums.push_back(cur->val);travelsal(cur->right);}int kthSmallest(TreeNode* root, int k) {travelsal(root);return nums[k - 1];}
};

199. 二叉树的右视图

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if(root!=nullptr) que.push(root);vector<int> result;while(!que.empty()){int size = que.size();for(int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();if(i == size - 1) result.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;}
};

114. 二叉树展开为链表

class Solution {
public:
TreeNode* traversal(TreeNode* root) {if (root == nullptr) return nullptr;TreeNode* cur = root;TreeNode* leftTree = traversal(root->left);TreeNode* rightTree = traversal(root->right);// 如果左子树存在if (leftTree != nullptr) {cur->right = leftTree;cur->left = nullptr;while (cur->right != nullptr) {cur = cur->right;  // 找到左子树的最右节点}cur->right = rightTree;  // 连接右子树} else {cur->right = rightTree;cur->left = nullptr;}return root;
}void flatten(TreeNode* root) {traversal(root);return;}
};

105. 从前序与中序遍历序列构造二叉树

class Solution {
public:TreeNode* traversal(vector<int>& preorder, vector<int>& inorder) {if(preorder.size() == 0) return nullptr;int rootvalue = preorder[0];TreeNode* root = new TreeNode(rootvalue);int mid;for(mid = 0; mid < inorder.size(); mid++) {if(inorder[mid] == rootvalue) {break;}} vector<int> inorderLeft(inorder.begin(), inorder.begin() + mid);vector<int> inorderRight(inorder.begin() + mid + 1, inorder.end());vector<int> preorderLeft(preorder.begin() + 1, preorder.begin() + inorderLeft.size() + 1);vector<int> preorderRight(preorder.begin() + 1 + inorderLeft.size(),preorder.end());root->left = traversal(preorderLeft, inorderLeft);root->right = traversal(preorderRight, inorderRight);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return traversal(preorder, inorder);}
};