leetcode/Binary_Tree_Postorder_Traversal.cpp at master · panzg123/leetcode · GitHub

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Solution
{
public:
    /*用栈，用flag来记录是否被访问*/
    vector<int> postorderTraversal(TreeNode* root)
    {
        typedef struct node_flag
        {
            TreeNode *node;
            int flag = 0;
            node_flag(TreeNode * val) :node(val) {}
        };
        stack<node_flag> stack_tree;
        vector<int> result;
        if (root == nullptr)
            return result;
        node_flag flag_root(root);
        stack_tree.push(flag_root);

        while (!stack_tree.empty())
            {
                node_flag  ptr_tree = stack_tree.top();
                if (ptr_tree.flag == 1)
                    result.push_back(ptr_tree.node->val);
                stack_tree.pop();

                int left_flag = ptr_tree.flag;
                if (ptr_tree.flag == 0)
                    {
                        ptr_tree.flag = 1;
                        stack_tree.push(ptr_tree);
                    }

                if (ptr_tree.node->right != nullptr && left_flag == 0)
                    {
                        node_flag flag_right(ptr_tree.node->right);
                        stack_tree.push(flag_right);
                    }


                if (ptr_tree.node->left != nullptr && left_flag == 0)
                    {
                        node_flag flag_left(ptr_tree.node->left);
                        stack_tree.push(flag_left);
                    }

            }
        return result;
    }
    // Morris 后序遍历，时间复杂度 O(n)，空间复杂度 O(1)
    vector<int> postorderTraversal(TreeNode *root)
    {
        vector<int> result;
        TreeNode dummy(-1);
        TreeNode *cur, *prev = nullptr;
        std::function < void(const TreeNode*)> visit =
            [&result](const TreeNode *node)
        {
            result.push_back(node->val);
        };
        dummy.left = root;
        cur = &dummy;
        while (cur != nullptr)
            {
                if (cur->left == nullptr)
                    {
                        prev = cur; /* 必须要有 */
                        cur = cur->right;
                    }
                else
                    {
                        TreeNode *node = cur->left;
                        while (node->right != nullptr && node->right != cur)
                            node = node->right;
                        if (node->right == nullptr)   /* 还没线索化，则建立线索 */
                            {
                                node->right = cur;
                                prev = cur; /* 必须要有 */
                                cur = cur->left;
                            }
                        else     /* 已经线索化，则访问节点，并删除线索 */
                            {
                                visit_reverse(cur->left, prev, visit);
                                prev->right = nullptr;
                                prev = cur; /* 必须要有 */
                                cur = cur->right;
                            }
                    }
            }
        return result;
    }
private:
	// 逆转路径
    static void reverse(TreeNode *from, TreeNode *to)
    {
        TreeNode *x = from, *y = from->right, *z;
        if (from == to) return;
        while (x != to)
            {
                z = y->right;
                y->right = x;
                x = y;
                y = z;
            }
    }
	// 访问逆转后的路径上的所有结点
    static void visit_reverse(TreeNode* from, TreeNode *to,
                              std::function< void(const TreeNode*) >& visit)
    {
        TreeNode *p = to;
        reverse(from, to);
        while (true)
            {
                visit(p);
                if (p == from)
                    break;
                p = p->right;
            }
        reverse(to, from);
    }
};