深度优先先序遍历二叉树
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 };