中序遍历二叉树,8年前CPP做过,现在Python再刷一遍
CPP版
1 //94
2 //Runtime: 8 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 class Solution {
14 public:
15 vector<int> res;
16
17 void inorder(TreeNode *root) {
18 if(root->left != NULL) inorder(root->left);
19 res.push_back(root->val);
20 if(root->right != NULL) inorder(root->right);
21 }
22
23 vector<int> inorderTraversal(TreeNode *root) {
24 res.clear();
25 if(root == NULL) return res;
26 inorder(root);
27 return res;
28 }
29 };
Python版
1 #94
2 #Runtime: 27 ms
3 #Memory Usage: 13.4 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 self.DFS(r.left, ans)
16 ans.append(r.val)
17 self.DFS(r.right, ans)
18 return ans
19
20 def inorderTraversal(self, root):
21 """
22 :type root: TreeNode
23 :rtype: List[int]
24 """
25 return self.DFS(root, [])