中煤第三建设集团投标网站,购物网站排行榜前十名,wap建站程序免费下载,推广网站制作怎么做文章目录二叉树2. 递归遍历二叉树3. 二叉树的迭代遍历4. 二叉树的统一迭代法二叉树
2. 递归遍历二叉树
144. 二叉树的前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;preorder(root, result);return res…
文章目录二叉树2. 递归遍历二叉树3. 二叉树的迭代遍历4. 二叉树的统一迭代法二叉树
2. 递归遍历二叉树
144. 二叉树的前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;preorder(root, result);return result;}private:void preorder(TreeNode *root, vectorint result) {if (root NULL) return ;result.push_back(root-val);preorder(root-left, result);preorder(root-right, result);}
};94. 二叉树的中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;inorder(root, result);return result;}private:void inorder(TreeNode *root, vectorint result) {if (root NULL) return ;inorder(root-left, result);result.push_back(root-val);inorder(root-right, result);}
};145. 二叉树的后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint result;postorder(root, result);return result;}private:void postorder(TreeNode *root, vectorint result) {if (root NULL) return ;postorder(root-left, result);postorder(root-right, result);result.push_back(root-val);}
};3. 二叉树的迭代遍历
144. 二叉树的前序遍历 遍历顺序中左右 压栈顺序中直接弹出右左 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;if (root NULL) return result;stackTreeNode * stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur stk.top();stk.pop();result.push_back(cur-val); // 中if (cur-right) stk.push(cur-right); // 右if (cur-left) stk.push(cur-left); // 左}return result;}
};145. 二叉树的后序遍历 先序遍历中左右 后序遍历左右中 所以把先序遍历的压栈顺序修改得到遍历 中右左 的顺序然后翻转遍历结果。 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint result;if (root NULL) return result;stackTreeNode * stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur stk.top();stk.pop();result.push_back(cur-val); // 中if (cur-left) stk.push(cur-left); // 左if (cur-right) stk.push(cur-right); // 右}reverse(result.begin(), result.end()); // 此时遍历顺序为 中右左翻转得到后序遍历的结果return result;}
};94. 二叉树的中序遍历 中序遍历不太一样要借助指针查看左子节点是否为空来得到左中右的遍历结果 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode * stk;TreeNode *cur root;while ( cur ! NULL || !stk.empty() ) {if (cur ! NULL) { // 如果当前节点不空则一直找左子节点stk.push(cur);cur cur-left;} else {cur stk.top(); // 上个节点的左节点已经找完了stk.pop();result.push_back(cur-val); // 左完了该中cur cur-right; // 中完了去看右子树}}return result;}
};4. 二叉树的统一迭代法
统一遍历方式按遍历顺序的逆序输出结果。
144. 二叉树的前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;stackTreeNode * stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur stk.top();stk.pop();if (cur) { // 遇到 null 说明是待处理节点if (cur-right) stk.push(cur-right); // 右if (cur-left) stk.push(cur-left); // 左stk.push(cur); // 中stk.push(NULL); // 标记节点} else { // 遇到 NULL 标记开始处理节点cur stk.top(); // 取出被标记的待处理节点result.push_back(cur-val);stk.pop();}}return result;}
};94. 二叉树的中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode * stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur stk.top();stk.pop();if (cur) {if (cur-right) stk.push(cur-right); // 右stk.push(cur); // 中stk.push(NULL); // 标记if (cur-left) stk.push(cur-left); // 左} else {cur stk.top();result.push_back(cur-val);stk.pop();}}return result;}
};145. 二叉树的后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint result;stackTreeNode * stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur stk.top();stk.pop();if (cur) {stk.push(cur);stk.push(NULL);if (cur-right) stk.push(cur-right);if (cur-left) stk.push(cur-left); } else {cur stk.top();result.push_back(cur-val);stk.pop();}}return result;}
};
