首页 > 代码库 > 【算法模板】二叉树
【算法模板】二叉树
模板:
1.先序遍历三种方法
1)迭代:
class Solution { public: /** * @param root: The root of binary tree. * @return: Preorder in vector which contains node values. */ vector<int> preorderTraversal(TreeNode *root) { vector<int> res; stack<TreeNode*> stack; if (root == NULL) { return res; } stack.push(root); while (!stack.empty()) { TreeNode *node = stack.top(); stack.pop(); res.push_back(node->val); if (node->right != NULL) { stack.push(node->right); } if (node->left != NULL) { stack.push(node->left); } } return res; } };
2)递归:
class Solution { public: void traversal(TreeNode *root, vector<int>& res) { if (root == NULL) { return; } res.push_back(root->val); traversal(root->left, res); traversal(root->right, res); } vector<int> preorderTraversal(TreeNode *root) { vector<int> res; traversal(root, res); return res; } };
3)分治:
class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> res; if (root == NULL) { return res; } vector<int> left = preorderTraversal(root->left); vector<int> right = preorderTraversal(root->right); res.push_back(root->val); res.insert(res.end(), left.begin(), left.end()); res.insert(res.end(), right.begin(), right.end()); return res; } };
【算法模板】二叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。