什么网站可以做推广的,网页设计策划方案,it外包服务公司排名,西安建设科技专修学院网站目录
一、认识二叉树
1. 二叉树的种类
#xff08;1#xff09;满二叉树
#xff08;2#xff09;完全二叉树
#xff08;3#xff09;二叉搜索树
#xff08;4#xff09;平衡二叉搜索树
2. 二叉树的存储方式
3. 二叉树的遍历方式
4. 二叉树的定义
二、Leet…目录
一、认识二叉树
1. 二叉树的种类
1满二叉树
2完全二叉树
3二叉搜索树
4平衡二叉搜索树
2. 二叉树的存储方式
3. 二叉树的遍历方式
4. 二叉树的定义
二、Leetcode 题目整理
1. 二叉树的前、中、后序遍历
1递归法
2迭代法栈的运用
3标记法栈的运用
2. 二叉树的层序遍历
1递归法
2迭代法
3. 翻转二叉树
1广度优先算法
2深度优先算法前、中、后
3递归法
4. 对称二叉树
1递归法
2迭代法
5. 二叉树的最大深度
6. 二叉树的最小深度
7. 平衡二叉树
8. 二叉树的所有路径
1回溯法
2迭代法 一、认识二叉树
1. 二叉树的种类
1满二叉树 深度为 k有 2^k-1 个节点的二叉树。 2完全二叉树 在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层h从1开始则该层包含 1~ 2^(h-1) 个节点。 3二叉搜索树 二叉搜索树是一个有序树。 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树 4平衡二叉搜索树 C 中 map、set、multimapmultiset 的底层实现都是 平衡二叉搜索树所以map、set 的增删操作 时间时间复杂度 是 logn。 2. 二叉树的存储方式 二叉树可以链式存储也可以顺序存储。 链式存储方式就用 指针 顺序存储的方式就是用 数组。 在数组存储中如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。 3. 二叉树的遍历方式 二叉树主要有两种遍历方式 深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。 从深度优先遍历和广度优先遍历进一步拓展才有如下遍历方式 深度优先遍历 前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法广度优先遍历 层次遍历迭代法 4. 二叉树的定义
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; 二、Leetcode 题目整理 1. 二叉树的前、中、后序遍历
144. 二叉树的前序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/566103571/94. 二叉树的中序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-inorder-traversal/description/145. 二叉树的后序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-postorder-traversal/description/ 给你二叉树的根节点 root 返回它节点值的 前序 / 中序 / 后序遍历。 1递归法
/*** Definition for a binary tree node.* 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) {}* };*/// 前序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint result) {if (cur NULL) return;result.push_back(cur-val);traversal(cur-left, result);traversal(cur-right, result);}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};// 中序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint result) {if (cur NULL) return;traversal(cur-left, result);result.push_back(cur-val);traversal(cur-right, result);}vectorint inorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};// 后序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint result) {if (cur NULL) return;traversal(cur-left, result);traversal(cur-right, result);result.push_back(cur-val);}vectorint postorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};2迭代法栈的运用
/*** Definition for a binary tree node.* 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) {}* };*/// 前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* record;vectorint result;if (root NULL) return result;record.push(root);while (!record.empty()) {TreeNode* node record.top();record.pop();result.push_back(node-val);if (node-right) record.push(node-right);if (node-left) record.push(node-left);}return result;}
};// 中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur);cur cur-left;} else {cur st.top(); // 从栈里弹出的数据就是要处理的数据放进result数组里的数据st.pop();result.push_back(cur-val);cur cur-right;}}return result;}
};// 后序遍历前序输出后翻转就可以
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();result.push_back(node-val);if (node-left) st.push(node-left); // 相对于前序遍历这更改一下入栈顺序 空节点不入栈if (node-right) st.push(node-right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};
3标记法栈的运用 将访问的节点放入栈中把要处理的节点也放入栈中但是要做标记。如何标记呢就是要处理的节点放入栈之后紧接着放入一个空指针作为标记。 /*** Definition for a binary tree node.* 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) {}* };*/// 前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* record;if (root ! nullptr) record.push(root);while (!record.empty()) {TreeNode* node record.top();if (node ! nullptr) {record.pop();if (node-right) record.push(node-right);if (node-left) record.push(node-left);record.push(node);record.push(nullptr);}else {record.pop();node record.top();record.pop();result.push_back(node-val);}}return result;}
};// 中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {// 标记法vectorint result;stackTreeNode* record;if (root ! nullptr) record.push(root);while (!record.empty()) {TreeNode* node record.top(); // 等于nullptr说明最先处理的节点已经遍历到。叶子结点已经到底需要打印中间节点// 不等于nullptr说明还未遍历到最先处理的节点if (node ! nullptr) {record.pop(); // 弹出顶部元素避免重复if (node-right) record.push(node-right);record.push(node);record.push(nullptr);if (node-left) record.push(node-left);}else {record.pop(); // 弹出nullptrnode record.top();record.pop();result.push_back(node-val);}}return result;}
};// 后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* record;if (root ! nullptr) record.push(root);while (!record.empty()) {TreeNode* node record.top();if (node ! nullptr) {// 中 nullptr 右 左record.push(nullptr);if (node-right) record.push(node-right);if (node-left) record.push(node-left);}else {record.pop();node record.top();record.pop();result.push_back(node-val);}}return result;}
};
2. 二叉树的层序遍历
102. 二叉树的层序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-level-order-traversal/description/ 给你一个二叉树请你返回其按 层序遍历 得到的节点值。 即逐层地从左到右访问所有节点。 示例 1
输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[]
1递归法
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:void order(TreeNode* cur, vectorvectorint result, int depth){if (cur nullptr) return;// 二叉树的层级是递增的从根节点开始逐层向下且每个层级只会在第一次遇到时执行这行代码// 因此每个层级只会被添加一次对应的 vectorint()if (result.size() depth) result.push_back(vectorint());result[depth].push_back(cur-val);order(cur-left, result, depth 1);order(cur-right, result, depth 1);}vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;int depth 0;order(root, result, depth);return result;}
};
2迭代法
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result;queueTreeNode* que;if (root ! nullptr) que.push(root);while (!que.empty()) {// 现在que队列中的元素为当前层的节点个数int size que.size();vectorint record;for (int i 0; i size; i) {TreeNode* node que.front();que.pop();record.push_back(node-val);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}result.push_back(record);}return result;}
};
3. 翻转二叉树
226. 翻转二叉树 - 力扣LeetCodehttps://leetcode.cn/problems/invert-binary-tree/description/ 给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。 示例 1
输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2
输入root [2,1,3]
输出[2,3,1]示例 3
输入root []
输出[] 想要翻转它其实就把每一个节点的左右孩子交换一下就可以了。 1广度优先算法
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 层序遍历if (!root || (!root-left !root-right)) return root;queueTreeNode* que;que.push(root);while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();swap(node-left, node-right);if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return root;}
};
2深度优先算法前、中、后
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 后序遍历循环法stackTreeNode* record;if (root ! nullptr) record.push(root);while (!record.empty()) {TreeNode* node record.top();record.pop();if (node ! nullptr) {// 栈顶元素不等于 nullptrrecord.push(node); // 中 record.push(nullptr); // 到遍历中节点的时候停一下需要先遍历右节点if (node-right) record.push(node-right); // 右if (node-left) record.push(node-left); // 左}else {node record.top();record.pop();swap(node-left, node-right);}}return root;}
};class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 中序遍历循环法stackTreeNode* record;if (root ! nullptr) record.push(root);while (!record.empty()) {TreeNode* node record.top();record.pop();if (node ! nullptr) {// 栈顶元素不等于 nullptrif (node-right) record.push(node-right); // 右record.push(node); // 中 record.push(nullptr); // 遍历完左节点的时候停一下现处理中节点if (node-left) record.push(node-left); // 左}else {node record.top();record.pop();swap(node-left, node-right);}}return root;}
};class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 前序遍历循环法stackTreeNode* record;if (root ! nullptr) record.push(root);while (!record.empty()) {TreeNode* node record.top();record.pop();if (node ! nullptr) {// 栈顶元素不等于 nullptrif (node-right) record.push(node-right); // 右if (node-left) record.push(node-left); // 左record.push(node); // 中 record.push(nullptr);}else {node record.top();record.pop();swap(node-left, node-right);}}return root;}
};
3递归法
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root NULL) return root;swap(root-left, root-right); // 中invertTree(root-left); // 左invertTree(root-right); // 右return root;}
};
4. 对称二叉树
101. 对称二叉树 - 力扣LeetCodehttps://leetcode.cn/problems/symmetric-tree/description/ 给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1
输入root [1,2,2,3,4,4,3]
输出true 示例 2
输入root [1,2,2,null,3,null,3]
输出false
1递归法 ① 终止条件 左节点为空右节点不为空不对称return false左不为空右为空不对称 return false左右都为空对称返回true ② 单层递归的逻辑 单层递归的逻辑就是处理 左右节点都不为空且数值相同的情况。 比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。比较内侧是否对称传入左节点的右孩子右节点的左孩子。如果左右都对称就返回 true 有一侧不对称就返回 false 。 /*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {// 判断条件if (left nullptr right ! nullptr) return false;else if (left ! nullptr right nullptr) return false;else if (left nullptr right nullptr) return true;else if (left-val ! right-val) return false;bool outside compare(left-left, right-right); // 外层判断bool inside compare(left-right, right-left); // 内层判断return (outside inside);}bool isSymmetric(TreeNode* root) {// 递归法if (root nullptr) return true;return compare(root-left, root-right);}
};
2迭代法 通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等。 /*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root nullptr) return true;queueTreeNode* que;que.push(root-left);que.push(root-right);while (!que.empty()) {TreeNode* leftnode que.front(); que.pop();TreeNode* rightnode que.front(); que.pop();if (leftnode nullptr rightnode ! nullptr) return false;else if (leftnode ! nullptr rightnode nullptr) return false;else if (leftnode nullptr rightnode nullptr) continue;else if (leftnode-val ! rightnode-val) return false;// 填入数据que.push(leftnode-left);que.push(rightnode-right);que.push(leftnode-right);que.push(rightnode-left);}return true;}
};
5. 二叉树的最大深度
104. 二叉树的最大深度 - 力扣LeetCodehttps://leetcode.cn/problems/maximum-depth-of-binary-tree/description/ 给定一个二叉树 root 返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1
输入root [3,9,20,null,null,15,7]
输出3示例 2
输入root [1,null,2]
输出2
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {// 二叉树层序遍历queueTreeNode* que;int depth 0;if (root NULL) return depth;que.push(root);while(!que.empty()) {int size que.size();depth; // 记录深度for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return depth;}
};
6. 二叉树的最小深度
111. 二叉树的最小深度 - 力扣LeetCodehttps://leetcode.cn/problems/minimum-depth-of-binary-tree/description/ 给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明叶子节点是指没有子节点的节点。 示例 1
输入root [3,9,20,null,null,15,7]
输出2示例 2
输入root [2,null,3,null,4,null,5,null,6]
输出5
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {// 层序遍历int depth 0;queueTreeNode* que;if (root NULL) return 0;que.push(root);while(!que.empty()) {int size que.size();depth; // 记录最小深度for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if (node-left) que.push(node-left);if (node-right) que.push(node-right);if (!node-left !node-right) { // 当左右孩子都为空的时候说明是最低点的一层了退出return depth;}}}return depth;}
};
7. 平衡二叉树
110. 平衡二叉树 - 力扣LeetCodehttps://leetcode.cn/problems/balanced-binary-tree/description/ 给定一个二叉树判断它是否是 平衡二叉树。 示例 1
输入root [3,9,20,null,null,15,7]
输出true 示例 2
输入root [1,2,2,3,3,null,null,4,4]
输出false
示例 3
输入root []
输出true 思路 1明确递归函数的参数 和 返回值 参数当前传入节点。 返回值以当前传入节点为根节点的树的高度。 如果已经不是二叉平衡树了可以返回-1 来标记已经不符合平衡树的规则了。 2明确终止条件 递归的过程中 依然是遇到 空节点了为终止返回 0表示 当前节点为 根节点的 树高度为0。 3明确单层递归的逻辑 分别求出其左右子树的高度然后如果差值小于 等于1则返回当前二叉树的高度否则返回-1表示已经 不是二叉平衡树了。 /*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:int getHeight(TreeNode* node) { // 后序遍历if (node nullptr) return 0;int leftNum getHeight(node-left);if (leftNum -1) return -1;int rightNum getHeight(node-right);if (rightNum -1) return -1;// 子树拥有的层数越多高度越高return abs(leftNum - rightNum) 1 ? -1 : 1 max(leftNum, rightNum);}bool isBalanced(TreeNode* root) {// 回溯法return getHeight(root) -1 ? false : true;}
};
8. 二叉树的所有路径
257. 二叉树的所有路径 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-paths/description/ 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。 示例 1
输入root [1,2,3,null,5]
输出[1-2-5,1-3]示例 2
输入root [1]
输出[1]
1回溯法 这道题目要求 从根节点到叶子的路径所以需要 前序遍历这样才 方便让父节点 指向孩子 节点找到 对应的路径。我们 要把路径 记录下来需要 回溯来回退一个 路径 再进入另一个路径。 /*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:void TreePath(TreeNode* node, vectorstring path, string str) {str str to_string(node-val);if (!node-left !node-right) {path.push_back(str);return;}if (node-left) TreePath(node-left, path, str -);if (node-right) TreePath(node-right, path, str -);}vectorstring binaryTreePaths(TreeNode* root) {// 前序遍历vectorstring result;if (root nullptr) return result;TreePath(root, result, );return result;}
};
2迭代法
/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:vectorstring binaryTreePaths(TreeNode* root) {stackTreeNode* treeSt;// 保存树的遍历节点stackstring pathSt; // 保存遍历路径的节点vectorstring result; // 保存最终路径集合if (root NULL) return result;treeSt.push(root);pathSt.push(to_string(root-val));while (!treeSt.empty()) {TreeNode* node treeSt.top(); treeSt.pop(); // 取出节点 中string path pathSt.top();pathSt.pop(); // 取出该节点对应的路径if (node-left NULL node-right NULL) { // 遇到叶子节点result.push_back(path);}if (node-right) { // 右treeSt.push(node-right);pathSt.push(path - to_string(node-right-val));}if (node-left) { // 左treeSt.push(node-left);pathSt.push(path - to_string(node-left-val));}}return result;}
};
