加强网站信息建设网站开发学生鉴定表

加强网站信息建设,网站开发学生鉴定表,网站域名包括,相册网站怎么做目录 二叉树遍历分为两大类#xff1a; 二叉树节点结构 深度优先遍历#xff08;DFS#xff09; 二叉树前序递归遍历 二叉树前序非递归遍历 二叉树中序递归遍历 二叉树中序非递归遍历 二叉树后序递归遍历 二叉树后序非递归遍历 广度优先遍历#xff08;BFS#…目录二叉树遍历分为两大类二叉树节点结构深度优先遍历DFS二叉树前序递归遍历二叉树前序非递归遍历二叉树中序递归遍历二叉树中序非递归遍历二叉树后序递归遍历二叉树后序非递归遍历广度优先遍历BFS二叉树的层序遍历二叉树遍历分为两大类深度优先遍历DFS前序、中序、后序广度优先遍历BFS层次遍历掌握二叉树的遍历是理解和操作二叉树的基础。递归方法简洁易懂迭代方法效率更高且避免栈溢出二叉树节点结构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) {} };深度优先遍历DFS二叉树前序递归遍历vectorint preorderTraversal(TreeNode* root) { vectorint result; preorder(root, result); return result; } void preorder(TreeNode* root, vectorint result) { if (!root) return; result.push_back(root-val); // 访问根 preorder(root-left, result); // 遍历左子树 preorder(root-right, result); // 遍历右子树 }二叉树前序非递归遍历思路前序非递归遍历需要借助栈1. 如果树为空直接返回2. 如果树非空从根节点位置开始遍历因为前序遍历规则根节点、左子树、右子树a. 沿着根节点一直往左走将所经过路径中的节点依次入栈并访问。b. 取栈顶元素该元素取到后其左子树要么为空要么已经遍历可以直接遍历该节点对于该节点其左子树已经遍历该节点也已经遍历剩余其右子树没有遍历将其左子树当成一棵新的树开始遍历继续a代码实现class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint v; stackTreeNode* st; TreeNode* cur root; while(!st.empty() || cur) { // 每次循环表示要开始访问一颗树了先将一颗数的左路节点都入栈并访问节点 // 剩余左路节点的右子树还没访问 while(cur) { v.push_back(cur-val); st.push(cur); cur cur-left; } // 取栈中的节点依次访问左路节点的右子树 TreeNode* top st.top(); st.pop(); cur top-right; } return v; } };二叉树中序递归遍历vectorint inorderTraversal(TreeNode* root) { vectorint result; inorder(root, result); return result; } void inorder(TreeNode* root, vectorint result) { if (!root) return; inorder(root-left, result); // 遍历左子树 result.push_back(root-val); // 访问根 inorder(root-right, result); // 遍历右子树 }二叉树中序非递归遍历思路中序非递归遍历需要借助栈 1. 空树直接返回 2. 如果树非空从根节点位置开始遍历但此时根节点不能遍历因为中序遍历规则左子树、根节点、右子树 a. 沿着根节点一直往左走将所经过路径中的节点依次入栈 b. 取栈顶元素该元素取到后其左子树要么为空要么已经遍历可以直接遍历该节点对于该节点其左子树已经遍历该节点也已经遍历剩余其右子树没有遍历将其左子树当成一棵新的树开始遍历继续a代码实现class Solution { public: vectorint inorderTraversal(TreeNode* root) { // 空树直接返回 vectorint vRet; if(nullptr root) return vRet; TreeNode* pCur root; stackTreeNode* s; while(pCur || !s.empty()) { // 找以pCur为根的二叉树最左侧的节点并将所经路径中的节点入栈 while(pCur) { s.push(pCur); pCur pCur-left; } pCur s.top(); // pCur左子树为空相当于左子树已经访问过了可以直接访问以pCur为根的二叉树的根节点 vRet.push_back(pCur-val); s.pop(); // 以pCur为根的二叉树的左子树已经遍历完根节点已经遍历 // 将pCur的右子树当成一棵二叉树来遍历 pCur pCur-right; } return vRet; } };二叉树后序递归遍历vectorint postorderTraversal(TreeNode* root) { vectorint result; postorder(root, result); return result; } void postorder(TreeNode* root, vectorint result) { if (!root) return; postorder(root-left, result); // 遍历左子树 postorder(root-right, result); // 遍历右子树 result.push_back(root-val); // 访问根 }二叉树后序非递归遍历思路后序非递归遍历需要借助栈 1. 空树直接返回 2. 如果树非空从根节点位置开始遍历但此时根节点不能遍历因为后序遍历规则左子树、右子树、根节点 a. 沿着根节点一直往左走将所经过路径中的节点依次入栈 b. 取栈顶元素该元素取到后其左子树要么为空要么已经遍历但是此时该节点不能遍历除非其右子树不存在或者其右子树已经遍历才可以遍历该节点.如果该节点右子树没有遍历将其右子树作为一棵新的二叉树遍历继续a代码实现class Solution { public: vectorint postorderTraversal(TreeNode* root) { // 空树直接返回 vectorint vRet; if(nullptr root) return vRet; TreeNode* pCur root; TreeNode* pPrev nullptr; stackTreeNode* s; while(pCur || !s.empty()) { // 找以pCur为根的二叉树最左侧的节点并将所经路径中的节点入栈 while(pCur) { s.push(pCur); pCur pCur-left; } TreeNode* pTop s.top(); // pTop左子树已经访问 // 如果pTop的右子树是空或者右子树已经访问过了就可以访问pTop if(nullptr pTop-right || pPrev pTop-right) { vRet.push_back(pTop-val); s.pop(); // 将刚刚访问过的节点标记起来 pPrev pTop; } else { // 如果右子树没有访问将右子树当成一棵新的二叉树访问 pCur pTop-right; } } return vRet; } };广度优先遍历BFS二叉树的层序遍历层序遍历从上到下从左到右逐层访问二叉树的所有节点。通过这个性质我们可以联想到队列的FIFO特性保证了节点按入队顺序访问先入队的节点先访问符合层序要求vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); vectorint level; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }