首页 > 代码库 > Binary Tree Preorder Traversal
Binary Tree Preorder Traversal
思路一:采用递归的方法,每个节点访问一遍,时间复杂度O(n),空间复杂度O(n)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; preorder(root, result); return result; } void preorder(TreeNode *root, vector<int> &result) { if(root != nullptr) { result.push_back(root->val); if(root->left != nullptr) preorder(root->left, result); if(root->right != nullptr) preorder(root->right, result); } } };
思路二:非递归实现,过程中使用了栈,时间和空间复杂度同上
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode *> s; if(root != nullptr) { s.push(root); while(!s.empty()) { TreeNode *tmp = s.top(); s.pop(); result.push_back(tmp->val); if(tmp->right != nullptr) s.push(tmp->right); if(tmp->left != nullptr) s.push(tmp->left); } } return result; } };
思路三:采用morris遍历方式,时间复杂度同上,但是空间复杂度O(1):算法理解在此
关键在于将当前子树的中的最大值(最后遍历)的右指针指向根节点,以便于左边子树访问后后回溯到右子树
具体来说:
当当前节点左指针为空时,输出对应数值,回溯
当当前节点cur左指针非空,得到其左子树最大节点:当其右节点非空,输出对应数值,同时回溯,即将其右节点指向cur;若右节点非空,置空,遍历cur右子树
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; if(root == nullptr) return result; TreeNode *cur = root; while(cur != nullptr) { if(cur->left == nullptr) { result.push_back(cur->val); cur = cur->right; } else { TreeNode *tmp = cur->left; while(tmp->right != nullptr && tmp->right != cur) tmp = tmp->right; if(tmp->right == nullptr) { result.push_back(cur->val); tmp->right = cur; cur = cur->left; } else { tmp->right = nullptr; cur = cur->right; } } } return result; } };
Binary Tree Preorder Traversal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。