注册
登录
| 关键词： cur 节点 路径 root push result 迭代 right TreeNode 递归 |
二叉树的遍历（每一种遍历次序有递归实现（简捷）和迭代实现两种方式）  深度优先遍历1.递归实现 中根遍历的递归实现 vector vector inorder(root); return result; } void inorder(TreeNode* root){ if(root == nullptr){ return; } inorder(root->left); result.push_back(root->val); inorder(root->right); } 其他顺序的遍历只需调换顺序即可。 2.迭代实现 先根遍历（先序遍历） 例如下图中左边的单元，在先根遍历中，打印1，然后进入以2为根节点的下一个单元，倘若2为NULL，那么便进入3为根节点的下一个单元。  根节点→左子节点→右子节点,1,2,4,7,3,5,6,8  思路：迭代实现最重要的就是对路径的保存与回溯，如果不考虑上述内容，单单对每一次的迭代步骤进行实现，然后一路向下。 先根遍历实现的代码为： If(cur!= NULL) cout << cur->val; If(cur->left != NUll)cur=cur->left Else cur = cur->right; 加入对路径的记忆，将1到2的路径记为第一路径，将1到3的路径记为第二路径。将路径的终点按照第一路径在上，第二路径在下的顺序压入栈中。 加入对路径的记忆和提取 cur = s.top(); s.pop(); //从堆栈中提取路径 cout << cur->val; //打印，打印后的路径不用记忆 if(cur->right != NULL) s.push(cur->right); if(cur->left != NULL) s.push(cur->left); //记忆路径用于下一步的迭代 完整代码 vector vector stack< TreeNode *> s; TreeNode *cur; if(root != NULL){ s.push(root); } while(!s.empty()){ cur = s.top(); s.pop(); result.push_back(cur->val); if(cur->right != NULL) s.push(cur->right); if(cur->left != NULL) s.push(cur->left); } return result; } 中根遍历（中序遍历） 顾名思义，中根遍历的根位于结果序列的中间 左子节点→根节点→右子节点，4,7,2,1,3,5,8,6 以下图为例，在中根遍历中，直接进入以2为根节点的单元，若2为空，打印1，进入以3为根节点的单元。  先根遍历的基本逻辑实现为： If(cur!= nullptr) cur = cur->left Else cout << cur; cur = cur->right; 加入对于路径的记忆和提取,只需要在进入左子节点之前记录根节点即可。  If(cur != nullptr) { S.push_back(cur); cur = cur->left； }else { cur = s.top(); s.pop(); result.push_back(cur->val); cur = cur->right; } 完整代码为 vector vector stack const TreeNode *cur = root; while(!s.empty() || cur != nullptr){ if(cur!= nullptr) { s.push(cur); cur = cur->left; }else { cur = s.top(); s.pop(); result.push_back(cur->val); cur = cur->right; } } return result; } 后根遍历（后序遍历） 左子节点→右子节点→根节点 N、7、4、N、2、5、8、N、6、3、1  后根遍历和先根遍历的顺序是完全相反的，所以可以依据先根遍历的算法，得到结果后，再将结果反转过来即可。另外一种方法，太复杂，思路上屡不清，算了。 vector vector if (!root) return v; stack s.push(root); TreeNode *p = NULL; while(!s.empty()) { p = s.top(); s.pop(); v.insert(v.begin(), p->val); if (p->left) s.push(p->left); if (p->right) s.push(p->right); } return v; } |
| 本文出处： https://www.toutiao.com/a6664078790655738379/ |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
