aboutsummaryrefslogtreecommitdiff
path: root/binary_tree_postorder_trav.c
blob: 329199f331e0abd420e941187c9d4a13008a62cd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 145. Binary Tree Postorder Traversal
#include "leetcode.h"

/*
 * given the 'root' of a binary tree, return the postorder traversal of its
 * nodes' values
 */

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
  int *ans = (int *)malloc(100 * sizeof(int)), idx = 0;
  *returnSize = 0;
  struct TreeNode *stack[100] = {NULL};
  while (idx || root) {
    if (root) {
      stack[idx++] = root;
      ans[(*returnSize)++] = root->val;
      root = root->right;
    } else {
      struct TreeNode *node = stack[--idx];
      root = node->left;
    }
  }
  for (int i = 0, j = *returnSize - 1; i < j; i++, j--) {
    int tmp = ans[j];
    ans[j] = ans[i];
    ans[i] = tmp;
  }
  return ans;
}

int main() {
  struct TreeNode *root = treenode_create(1);
  root->right = treenode_create(2);
  root->right->left = treenode_create(3);
  int rs1, *pt1 = postorderTraversal(root, &rs1);
  for (int i = 0; i < rs1; i++)
    printf("%d ", pt1[i]); // expect: 3 2 1
  printf("\n");
  free(pt1);
}