首页 > 编程语言 > 详细

LeetCode 144. Binary Tree Preorder Traversal 二叉树的前序遍历 C++

时间:2019-04-05 17:13:12      阅读:146      评论:0      收藏:0      [点我收藏+]

Given a binary tree, return the preorder traversal of its nodes‘ values.

Example:

Input: [1,null,2,3]
   1
         2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

方法一:使用迭代(C++)

 1 vector<int> preorderTraversal(TreeNode* root) {
 2         vector<int> res={};
 3         if(!root)
 4             return res;
 5         stack<TreeNode*> s;
 6         TreeNode* cur=root;
 7         while(!s.empty()||cur){
 8             while(cur){
 9                 res.push_back(cur->val);
10                 s.push(cur);
11                 cur=cur->left;
12             }
13             cur=s.top();
14             s.pop();
15             cur=cur->right;
16         }
17         return res;
18     }

方法二:使用递归,更简单,但是效率较低

 1 void preOrder(TreeNode* root,vector<int>& m){
 2         if(!root)
 3             return;
 4         m.push_back(root->val);
 5         preOrder(root->left,m);
 6         preOrder(root->right,m);
 7     }
 8     
 9     vector<int> preorderTraversal(TreeNode* root) {
10         vector<int> res={};
11         if(!root)
12             return res;
13         preOrder(root,res);
14         return res;
15     }

 

LeetCode 144. Binary Tree Preorder Traversal 二叉树的前序遍历 C++

原文:https://www.cnblogs.com/hhhhan1025/p/10659136.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!