【leetcode】Binary Tree Postorder Traversal

地址

https://leetcode.com/problems/binary-tree-postorder-traversal/

题目

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
1
\
2
/
3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

思路

  1. 递归遍历

    做法简单好写。但题目要求使用迭代算法。

  2. 用栈迭代

    用栈模拟。

  3. 迭代做法

    可以google一下叫做“morris遍历”的东西,这是一种空间O(1),时间O(n)的二叉树迭代遍历算法。morris前序中序遍历都比较好些,但morris后序遍历难写一点,需要一个反向树链的操作。

PS: 我以为题目中说的迭代算法指的是让我用morris遍历,写完了才发现迭代好像还有种用栈模拟傻逼做法。。。

代码

  1. 做法一

    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
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    * int val;
    * TreeNode *left;
    * TreeNode *right;
    * TreeNode() : val(0), left(nullptr), right(nullptr) {}
    * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
    class Solution {
    public:
    vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    if(root != NULL)
    dfs(root, ans);
    return ans;
    }

    void dfs(TreeNode* p, vector<int> &ans)
    {
    if(p->left != NULL)
    dfs(p->left, ans);
    if(p->right != NULL)
    dfs(p->right, ans);
    ans.push_back(p->val);
    }
    };
  2. 做法二

    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
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    * int val;
    * TreeNode *left;
    * TreeNode *right;
    * TreeNode() : val(0), left(nullptr), right(nullptr) {}
    * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
    class Solution {
    public:
    vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    TreeNode *last, *cur = root;
    while(cur != NULL)
    {
    last = cur->left;
    if(last != NULL)
    {
    while(last->right != NULL && last->right != cur)
    last = last->right;
    //cout<<"=="<<cur->val<<endl;
    if(last->right == NULL)
    {
    last->right = cur;
    cur = cur->left;
    continue;
    }
    else
    {
    last->right = NULL;
    cout<<cur->left->val<<endl;
    print(cur->left, ans);
    }
    }
    cur = cur->right;
    }
    print(root, ans);
    return ans;

    }

    void print(TreeNode* cur, vector<int> &ans)
    {
    TreeNode* tail = reverse(cur);
    auto p = tail;
    //cout<<p->val<<endl;
    while(p != NULL)
    ans.push_back(p->val), p = p->right;
    reverse(tail);
    }
    TreeNode* reverse(TreeNode* cur)
    {
    TreeNode *pre = NULL, *tmp, *next;
    while(cur != NULL)
    {
    next = cur->right;
    cur->right = pre;
    pre = cur;
    cur = next;
    }
    return pre;
    }

    };