| Carl2.5 | 您所在的位置：网站首页 › carl2 › Carl2.5 |
Carl2.5
基础
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
2. 遍历
二叉树的前序遍历144
前序遍历在干路直接载入root，如第24行、43行
统一迭代：re.push_back(cur->val) 的位置保证每次写入“中”的值
//递归
class Solution {
public:
void traversal(TreeNode* cur, vector& vec) {
if (cur == NULL) return;
vec.push_back(cur->val);
traversal(cur->left,vec);
traversal(cur->right, vec);
}
vector preorderTraversal(TreeNode* root) {
vectorre;
traversal(root, re);
return re;
}
};
//迭代
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vectorre;
stackst;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
re.push_back(cur->val);
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
return re;
}
};
//统一迭代
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vectorre;
stackst;
st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
st.pop();
if (cur) {
st.push(cur);
st.push(NULL);
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
}
else {
cur = st.top();
st.pop();
re.push_back(cur->val);
}
}
return re;
}
};
二叉树的中序遍历94
//迭代
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
if (root == NULL) return {};
vectorre;
stackst;
TreeNode* cur = root;
while (cur||!st.empty()){
if (cur) {
st.push(cur);
cur = cur->left;
}
else {
cur = st.top();
st.pop();
re.push_back(cur->val);
cur = cur->right;
}
}
return re;
}
};
二叉树的后序遍历145
前序中左右->中右左->reverse为左右中
深度遍历总结
二叉树的层序遍历102
//递归
class Solution {
public:
void traversal(TreeNode* cur, vector& vec, int depth) {
if (cur == NULL) return;
if (depth == vec.size()) vec.push_back(vector());
vec[depth].push_back(cur->val);
traversal(cur->left, vec, depth + 1);
traversal(cur->right, vec, depth + 1);
}
vector levelOrder(TreeNode* root) {
vectorre;
if (root == NULL) return re;
traversal(root, re, 0);
return re;
}
};
//迭代
class Solution {
public:
vector levelOrder(TreeNode* root) {
if (root == NULL) return {};
vectorre;
queueque;
que.push(root);
while (!que.empty()) {
int size = que.size();
vectorvec;
for (int i = 0; i < size; ++i) {
TreeNode* cur = que.front();
que.pop();
vec.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
re.push_back(vec);
}
return re;
}
};
3. 应用
找树左下角的值513
最底层最左侧的值 可用于求最大深度 递归部分先left，因此每层必然是最左侧的叶子先被遍历，最后一层时直接返回 class Solution { public: int d = -1; int re; void traversal(TreeNode* cur, int depth) { if (cur->left == NULL && cur->right == NULL) { if (depth > d) { d = depth; re = cur->val; } return ; } if (cur->left) traversal(cur->left, depth + 1); if (cur->right) traversal(cur->right, depth + 1); return; } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return re; } }; 平衡二叉树110一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 //递归求高度 class Solution { public: int getHeight(TreeNode* node, int height) { height = 0; if (node == NULL) return height; int leftheight = getHeight(node->left, height + 1); int rightheight = getHeight(node->right, height + 1); height = leftheight > rightheight ? leftheight + 1 : rightheight + 1; return height; } bool isBalanced(TreeNode* root) { if (root == NULL) return true; stackst; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); if (cur) { st.push(cur); st.push(NULL); if (abs(getHeight(cur->left, 0) - getHeight(cur->right, 0)) > 1) return false; if (cur->right) st.push(cur->right); if (cur->left) st.push(cur->left); } else { cur = st.top(); st.pop(); } } return true; } }; //统一迭代求高度 int getHeight(TreeNode* node) { int height = 0; int re = 0; if (node == NULL) return height; stackst; st.push(node); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); if (cur) { st.push(cur); st.push(NULL); if (cur->right) st.push(cur->right); if (cur->left) st.push(cur->left); height++; } else { cur = st.top(); st.pop(); height--; } re = re > height ? re : height; } return re; } 路径总和112判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。 同步栈，若容器内容需要输出则用回溯 //递归 class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == NULL) return false; if (root->left == NULL && root->right == NULL && root->val == targetSum) return true; bool re = hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val); return re; } }; //同步栈 class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == NULL) return false; stackst; stacksum; st.push(root); sum.push(root->val); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); int scur = sum.top(); sum.pop(); if (cur->left == NULL && cur->right == NULL && scur == targetSum) return true; if (cur->left) { st.push(cur->left); sum.push(scur + cur->left->val); } if (cur->right) { st.push(cur->right); sum.push(scur + cur->right->val); } } return false; } }; 路径总和II 113找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 回溯，半递归 //回溯：vec无法同步 class Solution { public: vectorre; vectorvec; void traversal(TreeNode* cur, int count) { if (cur->left == NULL & cur->right == NULL && count == 0) { re.push_back(vec); return; } if (cur->left == NULL & cur->right == NULL) return; if (cur->left) { vec.push_back(cur->left->val); count -= cur->left->val; traversal(cur->left, count); count += cur->left->val; vec.pop_back(); } if (cur->right) { vec.push_back(cur->right->val); count -= cur->right->val; traversal(cur->right, count); count += cur->right->val; vec.pop_back(); } return; } vector pathSum(TreeNode* root, int targetSum) { if (root == NULL) return {}; vec.push_back(root->val); traversal(root, targetSum - root->val); return re; } }; 验证二叉搜索树98递归： // 将二叉搜索树转换为有序数组 vector vec; void traversal(TreeNode* root) { if (root == NULL) return; traversal(root->left); vec.push_back(root->val); traversal(root->right); }简化递归： class Solution { public: TreeNode* pre = NULL; bool isValidBST(TreeNode* root) { if (root == NULL) return true; bool left = isValidBST(root->left); if (pre != NULL && pre->val >= root->val) return false; pre = root; bool right = isValidBST(root->right); return left && right; } };中序 class Solution { public: bool isValidBST(TreeNode* root) { if (root == NULL) return true; stackst; TreeNode* cur = root; TreeNode* pre = NULL; while (cur || !st.empty()) { if (cur) { st.push(cur); cur = cur->left; } else { cur = st.top(); st.pop(); if (pre && pre->val >= cur->val) return false; pre = cur; cur = cur->right; } } return true; } }; 二叉搜索树中的插入操作701递归： class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) { TreeNode* node = new TreeNode(val); return node; } if (root->val > val) root->left = insertIntoBST(root->left, val); if (root->val < val) root->right = insertIntoBST(root->right, val); return root; } };递归： class Solution { private: TreeNode* parent; void traversal(TreeNode* cur, int val) { if (cur == NULL) { TreeNode* node = new TreeNode(val); if (val > parent->val) parent->right = node; else parent->left = node; return; } parent = cur; if (cur->val > val) traversal(cur->left, val); if (cur->val < val) traversal(cur->right, val); return; } public: TreeNode* insertIntoBST(TreeNode* root, int val) { parent = new TreeNode(0); if (root == NULL) root = new TreeNode(val); traversal(root, val); return root; } };迭代： class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { TreeNode* node = new TreeNode(val); if (root == nullptr) return node; TreeNode* pre = root; TreeNode* cur = pre; while (cur) { pre = cur; if (cur->val > val) cur = cur->left; else cur = cur->right; } if (pre->val < val) pre->right = node; else pre->left = node; return root; } }; 删除二叉搜索树中的节点450 class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) return root; if (root->val == key) { if (root->left == nullptr && root->right == nullptr) { delete root; return nullptr; } else if (root->left == nullptr) { auto retNode = root->right; delete root; return retNode; } else if (root->right == nullptr) { auto retNode = root->left; delete root; return retNode; } // 左右孩子都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置 // 并返回删除节点右孩子为新的根节点。 else { TreeNode* cur = root->right; while (cur->left) cur = cur->left; cur->left = root->left; TreeNode* tmp = root; root = root->right; delete tmp; return root; } } if (root->val > key) root->left = deleteNode(root->left, key); if (root->val < key) root->right = deleteNode(root->right, key); return root; } }; |
【本文地址】
公司简介
联系我们