Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
深度优先先序遍历二叉树

Python版

 1 #144
 2 #Runtime: 38 ms
 3 #Memory Usage: 13.5 MB
 4 
 5 # Definition for a binary tree node.
 6 # class TreeNode(object):
 7 #     def __init__(self, val=0, left=None, right=None):
 8 #         self.val = val
 9 #         self.left = left
10 #         self.right = right
11 class Solution(object):
12     def DFS(self, r, ans):
13         if not r:
14             return None
15         ans.append(r.val)
16         self.DFS(r.left, ans)
17         self.DFS(r.right, ans)
18         return ans
19     
20     def preorderTraversal(self, root):
21         """
22         :type root: TreeNode
23         :rtype: List[int]
24         """
25         return self.DFS(root, [])

CPP版

 1 //144
 2 //Runtime: 4 ms
 3 
 4 /**
 5  * Definition for binary tree
 6  * struct TreeNode {
 7  *     int val;
 8  *     TreeNode *left;
 9  *     TreeNode *right;
10  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11  * };
12  */
13  
14 vector<int> que;
15 
16 void pre_order(TreeNode *root) {
17     if(root == NULL) return;
18     que.push_back(root->val);
19     if(root->left != NULL) pre_order(root->left);
20     if(root->right != NULL) pre_order(root->right);
21 }
22     
23 class Solution {
24 public:
25     vector<int> preorderTraversal(TreeNode *root) {
26         if(!que.empty()) que.clear();
27         pre_order(root);
28         return que;
29     }
30 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理