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 #145
 2 #Runtime: 13 ms
 3 #Memory Usage: 13.6 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         self.DFS(r.right, ans)
17         ans.append(r.val)
18         return ans
19     
20     def postorderTraversal(self, root):
21         """
22         :type root: TreeNode
23         :rtype: List[int]
24         """
25         return self.DFS(root, [])

CPP版

 1 //145
 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 class Solution {
14 public:
15     TreeNode *tp[1010];
16     vector<int> postorderTraversal(TreeNode *root) {
17         int k = 0;
18         vector<int> que;
19         if(root == NULL) return que;
20         TreeNode *p = root, *pre = NULL;
21         tp[k++] = p;
22         while(k) {
23             TreeNode *cur = tp[k - 1];
24             if((cur->left == NULL && cur->right == NULL) || (pre != NULL && (pre == cur->left || pre == cur->right))) {
25                 que.push_back(cur->val);
26                 --k;
27                 pre = cur;
28             }
29             else {
30                 if(cur->right != NULL) tp[k++] = cur->right;
31                 if(cur->left != NULL) tp[k++] = cur->left;
32             }
33         }
34         return que;
35     }
36 };
37 
38 


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