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