0590-N 叉树的后序遍历

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

**输入：** root = [1,null,3,2,4,null,5,6]
**输出：** [5,6,3,2,4,1]

示例 2：

**输入：** root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
**输出：** [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

提示：

  • 节点总数在范围 [0, 104] 内
  • 0 <= Node.val <= 104
  • n 叉树的高度小于或等于 1000

进阶： 递归法很简单，你可以使用迭代法完成此题吗?

方法一：递归

思路

递归思路比较简单，N 叉树的前序遍历与二叉树的后序遍历的思路和方法基本一致，可以参考「145. 二叉树的后序遍历 」的方法，每次递归时，先递归访问每个孩子节点，然后再访问根节点即可。

代码

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(Node root, List<Integer> res) {
        if (root == null) {
            return;
        }
        for (Node ch : root.children) {
            helper(ch, res);
        }
        res.add(root.val);
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void helper(const Node* root, vector<int> & res) {
        if (root == nullptr) {
            return;
        }
        for (auto & ch : root->children) {
            helper(ch, res);
        }
        res.emplace_back(root->val);
    }

    vector<int> postorder(Node* root) {
        vector<int> res;
        helper(root, res);
        return res;
    }
};
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public IList<int> Postorder(Node root) {
        IList<int> res = new List<int>();
        Helper(root, res);
        return res;
    }

    public void Helper(Node root, IList<int> res) {
        if (root == null) {
            return;
        }
        foreach (Node ch in root.children) {
            Helper(ch, res);
        }
        res.Add(root.val);
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MAX_NODE_SIZE 10000

void helper(const struct Node* root, int* res, int* pos) {
    if (NULL == root) {
        return;
    }
    for (int i = 0; i < root->numChildren; i++) {
        helper(root->children[i], res, pos);
    }
    res[(*pos)++] = root->val;
}

int* postorder(struct Node* root, int* returnSize) {
    int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    int pos = 0;
    helper(root, res, &pos);
    *returnSize = pos;
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var postorder = function(root) {
    const res = [];
        helper(root, res);
        return res;
    }

const helper = (root, res) => {
    if (root == null) {
        return;
    }
    for (const ch of root.children) {
        helper(ch, res);
    }
    res.push(root.val);
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node: 'Node'):
            if node is None:
                return
            for ch in node.children:
                dfs(ch)
            ans.append(node.val)
        dfs(root)
        return ans
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func postorder(root *Node) (ans []int) {
    var dfs func(*Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        for _, ch := range node.Children {
            dfs(ch)
        }
        ans = append(ans, node.Val)
    }
    dfs(root)
    return
}

复杂度分析

  • 时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被遍历一次。

  • 空间复杂度：O(m)，递归过程中需要调用栈的开销，平均情况下为 O(\log m)，最坏情况下树的深度为 m-1，需要的空间为 O(m-1)，因此空间复杂度为 O(m)。

方法二：迭代

思路

方法一中利用递归来遍历树，实际的递归中隐式利用了栈，在此我们可以直接模拟递归中栈的调用。在后序遍历中从左向右依次先序遍历该每个以子节点为根的子树，然后先遍历节点本身。

在这里的栈模拟中比较难处理的在于从当前节点 u 的子节点 v_1 返回时，此时需要处理节点 u 的下一个节点 v_2，此时需要记录当前已经遍历完成哪些子节点，才能找到下一个需要遍历的节点。在二叉树树中因为只有左右两个子节点，因此比较方便处理，在 N 叉树中由于有多个子节点，因此使用哈希表记录当前节点 u 已经访问过哪些子节点。

  • 每次入栈时都将当前节点的 u 的第一个子节点压入栈中，直到当前节点为空节点为止。

  • 每次查看栈顶元素 p，如果节点 p 的子节点已经全部访问过，则记录当前节点的值，并将节点 p 的从栈中弹出，并从哈希表中移除，表示该以该节点的子树已经全部遍历过；如果当前节点 p 的子节点还有未遍历的，则将当前节点的 p 的下一个未访问的节点压入到栈中，重复上述的入栈操作。

代码

[sol2-Java]
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
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Map<Node, Integer> map = new HashMap<Node, Integer>();
        Deque<Node> stack = new ArrayDeque<Node>();
        Node node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                List<Node> children = node.children;
                if (children != null && children.size() > 0) {
                    map.put(node, 0);
                    node = children.get(0);
                } else {
                    node = null;
                }
            }
            node = stack.peek();
            int index = map.getOrDefault(node, -1) + 1;
            List<Node> children = node.children;
            if (children != null && children.size() > index) {
                map.put(node, index);
                node = children.get(index);
            } else {
                res.add(node.val);
                stack.pop();
                map.remove(node);
                node = null;
            }
        }
        return res;
    }
}
[sol2-C++]
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
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        
        unordered_map<Node *, int> cnt;
        stack<Node *> st;
        Node * node = root;
        while (!st.empty() || node != nullptr) {
            while (node != nullptr) {
                st.emplace(node);
                if (node->children.size() > 0) {
                    cnt[node] = 0;
                    node = node->children[0];
                } else {
                    node = nullptr;
                }         
            }
            node = st.top();
            int index = cnt.count(node) ? (cnt[node] + 1) : 0;
            if (index < node->children.size()) {
                cnt[node] = index;
                node = node->children[index];
            } else {
                res.emplace_back(node->val);
                st.pop();
                cnt.erase(node);
                node = nullptr;
            }
        }
        return res;
    }
};
[sol2-C#]
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
public class Solution {
    public IList<int> Postorder(Node root) {
        IList<int> res = new List<int>();
        if (root == null) {
            return res;
        }
        Dictionary<Node, int> dictionary = new Dictionary<Node, int>();
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        while (stack.Count > 0 || node != null) {
            while (node != null) {
                stack.Push(node);
                IList<Node> childrenList = node.children;
                if (childrenList != null && childrenList.Count > 0) {
                    dictionary.Add(node, 0);
                    node = childrenList[0];
                } else {
                    node = null;
                }
            }
            node = stack.Peek();
            int index = (dictionary.ContainsKey(node) ? dictionary[node] : -1) + 1;
            IList<Node> children = node.children;
            if (children != null && children.Count > index) {
                dictionary[node] = index;
                node = children[index];
            } else {
                res.Add(node.val);
                stack.Pop();
                dictionary.Remove(node);
                node = null;
            }
        }
        return res;
    }
}
[sol2-C]
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
#define MAX_NODE_SIZE 10000

typedef struct {
    void * key;
    int val;
    UT_hash_handle hh; 
} HashItem;

void freeHash(HashItem ** obj) {
    HashItem * curr = NULL, * next = NULL;
    HASH_ITER(hh, *obj, curr, next) {
        HASH_DEL(*obj, curr);
        free(curr);
    }
}

int* postorder(struct Node* root, int* returnSize) {
    if (NULL == root) {
        *returnSize = 0;
        return NULL;
    }
    int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    struct Node ** stack = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);
    int pos = 0, top = 0;  

    struct Node * node = root;
    HashItem * cnt = NULL;
    HashItem * pEntry = NULL;
    while (top != 0 || node != NULL) {
        while (node != NULL) {
            stack[top++] = node;
            if (node->numChildren > 0) {
                pEntry = (HashItem *)malloc(sizeof(HashItem));
                pEntry->key = node;
                pEntry->val = 0;
                HASH_ADD_PTR(cnt, key, pEntry);
                node = node->children[0];
            } else {
                node = NULL;
            }
        }
        node = stack[top - 1];
        int index = 0;
        HASH_FIND_PTR(cnt, &node, pEntry);
        if (pEntry != NULL) {
            index = pEntry->val + 1;
        }
        if (index < node->numChildren) {
            pEntry->val++;
            node = node->children[index];
        } else {
            top--;
            res[pos++] = node->val;
            if (pEntry != NULL) {
                HASH_DEL(cnt, pEntry);
            }
            node = NULL;
        }
    }
    free(stack);
    freeHash(&cnt);
    *returnSize = pos;
    return res;
}
[sol2-JavaScript]
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
var postorder = function(root) {
    const res = [];
    if (root == null) {
        return res;
    }
    const map = new Map();
    const stack = [];
    let node = root;
    while (stack.length || node) {
        while (node) {
            stack.push(node);
            const children = node.children;
            if (children && children.length > 0) {
                map.set(node, 0);
                node = children[0];
            } else {
                node = null;
            }
        }
        node = stack[stack.length - 1];
        const index = (map.get(node) || 0) + 1;
        const children = node.children;
        if (children && children.length > index) {
            map.set(node, index);
            node = children[index];
        } else {
            res.push(node.val);
            stack.pop();
            map.delete(node);
            node = null;
        }
    }
    return res;
};
[sol2-Python3]
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
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        ans = []
        st = []
        nextIndex = defaultdict(int)
        node = root
        while st or node:
            while node:
                st.append(node)
                if not node.children:
                    break
                nextIndex[node] = 1
                node = node.children[0]
            node = st[-1]
            i = nextIndex[node]
            if i < len(node.children):
                nextIndex[node] = i + 1
                node = node.children[i]
            else:
                ans.append(node.val)
                st.pop()
                del nextIndex[node]
                node = None
        return ans
[sol2-Golang]
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
func postorder(root *Node) (ans []int) {
    if root == nil {
        return
    }
    st := []*Node{}
    nextIndex := map[*Node]int{}
    node := root
    for len(st) > 0 || node != nil {
        for node != nil {
            st = append(st, node)
            if len(node.Children) == 0 {
                break
            }
            nextIndex[node] = 1
            node = node.Children[0]
        }
        node = st[len(st)-1]
        i := nextIndex[node]
        if i < len(node.Children) {
            nextIndex[node] = i + 1
            node = node.Children[i]
        } else {
            ans = append(ans, node.Val)
            st = st[:len(st)-1]
            delete(nextIndex, node)
            node = nil
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被访问一次。

  • 空间复杂度：O(m)，其中 m 为 N 叉树的节点。如果 N 叉树的深度为 1 则此时栈和哈希表的空间为 O(1)，如果 N 叉树的深度为 m-1 则此时栈和哈希表的空间为 O(m-1)，平均情况下栈和哈希表的空间为 O(\log m)，因此空间复杂度为 O(m)。

方法三：迭代优化

思路

在后序遍历中，我们会先从左向右依次后序遍历每个子节点为根的子树，再遍历根节点本身。此时利用栈先进后出的原理，依次从右向左将子节点入栈，这样出栈的时候即可保证从左向右依次遍历每个子树。参考方法二的原理，可以提前将后续需要访问的节点压入栈中。

首先把根节点入栈，因为根节点是前序遍历中的第一个节点。随后每次我们找到栈顶节点 u，如果当前节点的子节点没有遍历过，则应该先把 u 的所有子节点从右向左逆序压入栈中，这样出栈的节点则是顺序从左向右的，同时对节点 u 进行标记，表示该节点的子节点已经全部入栈；如果当前节点 u 为叶子节点或者当前节点的子节点已经全部遍历过，则从栈中弹出节点 u，并记录节点 u 的值。例如 u 的子节点从左到右为 v_1, v_2, v_3，那么入栈的顺序应当为 v_3, v_2, v_1，这样就保证了下一个遍历到的节点（即 u 的左侧第一个孩子节点 v_1）出现在栈顶的位置。此时，访问第一个子节点 v_1 时，仍然按照此方法则会先访问 v_1 的左侧第一个孩子节点。

代码

[sol3-Java]
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
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<Node>();
        Set<Node> visited = new HashSet<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.peek();
            /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
            if (node.children.size() == 0 || visited.contains(node)) {
                stack.pop();
                res.add(node.val);
                continue;
            }
            for (int i = node.children.size() - 1; i >= 0; --i) {
                stack.push(node.children.get(i));
            }
            visited.add(node);
        }
        return res;
    }
}
[sol3-C++]
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
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<Node *> st;
        unordered_set<Node *> visited;
        st.emplace(root);
        while (!st.empty()) {
            Node * node = st.top();
            /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
            if (node->children.size() == 0 || visited.count(node)) {
                res.emplace_back(node->val);
                st.pop();
                continue;
            }
            for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {
                st.emplace(*it);
            }
            visited.emplace(node);
        }       
        return res;
    }
};
[sol3-C#]
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
public class Solution {
    public IList<int> Postorder(Node root) {
        IList<int> res = new List<int>();
        if (root == null) {
            return res;
        }

        Stack<Node> stack = new Stack<Node>();
        ISet<Node> visited = new HashSet<Node>();
        stack.Push(root);
        while (stack.Count > 0) {
            Node node = stack.Peek();
            /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
            if (node.children.Count == 0 || visited.Contains(node)) {
                stack.Pop();
                res.Add(node.val);
                continue;
            }
            for (int i = node.children.Count - 1; i >= 0; i--) {
                stack.Push(node.children[i]);
            }
            visited.Add(node);
        }
        return res;
    }
}
[sol3-C]
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
#define MAX_NODE_SIZE 10000

typedef struct {
    void * key;
    UT_hash_handle hh; 
} HashItem;

void freeHash(HashItem ** obj) {
    HashItem * curr = NULL, * next = NULL;
    HASH_ITER(hh, *obj, curr, next) {
        HASH_DEL(*obj, curr);
        free(curr);
    }
}

int* postorder(struct Node* root, int* returnSize) {
    if (NULL == root) {
        *returnSize = 0;
        return NULL;
    }
    int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    struct Node ** stack = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);
    int pos = 0, top = 0;  

    stack[top++] = root;
    HashItem * visited = NULL;
    HashItem * pEntry = NULL;
    while (top != 0) {
        struct Node * node = stack[top - 1];
        pEntry = NULL;
        HASH_FIND_PTR(visited, &node, pEntry);
        /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
        if (node->numChildren == 0 || NULL != pEntry) {
            res[pos++] = node->val;
            top--;
            continue;
        }
        for (int i = node->numChildren - 1; i >= 0; i--) {
            stack[top++] = node->children[i];
        }
        pEntry = (HashItem *)malloc(sizeof(HashItem));
        pEntry->key = node;
        HASH_ADD_PTR(visited, key, pEntry);
    }
    free(stack);
    *returnSize = pos;
    return res;
}
[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var postorder = function(root) {
    const res = [];
    if (root == null) {
        return res;
    }

    const stack = [];
    const visited = new Set();
    stack.push(root);
    while (stack.length) {
        const node = stack[stack.length - 1];
        /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
        if (node.children.length === 0 || visited.has(node)) {
            stack.pop();
            res.push(node.val);
            continue;
        }
        for (let i = node.children.length - 1; i >= 0; --i) {
            stack.push(node.children[i]);
        }
        visited.add(node);
    }
    return res;
};
[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        ans = []
        st = [root]
        vis = set()
        while st:
            node = st[-1]
            # 如果当前节点为叶子节点或者当前节点的子节点已经遍历过
            if len(node.children) == 0 or node in vis:
                ans.append(node.val)
                st.pop()
                continue
            st.extend(reversed(node.children))
            vis.add(node)
        return ans
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func postorder(root *Node) (ans []int) {
    if root == nil {
        return
    }
    st := []*Node{root}
    vis := map[*Node]bool{}
    for len(st) > 0 {
        node := st[len(st)-1]
        // 如果当前节点为叶子节点或者当前节点的子节点已经遍历过
        if len(node.Children) == 0 || vis[node] {
            ans = append(ans, node.Val)
            st = st[:len(st)-1]
            continue
        }
        for i := len(node.Children) - 1; i >= 0; i-- {
            st = append(st, node.Children[i])
        }
        vis[node] = true
    }
    return
}

复杂度分析

  • 时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被访问一次。

  • 空间复杂度：O(m)，其中 m 为 N 叉树的节点。哈希表的空间为 O(m)，栈的空间与树的深度相同，栈的空间最大为 O(m-1)，因此空间复杂度为 O(m)。

方法四：利用前序遍历反转

思路

在前序遍历中，我们会先遍历节点本身，然后从左向右依次先序遍历该每个以子节点为根的子树，而在后序遍历中，需要先从左到右依次遍历每个以子节点为根的子树，然后再访问根节点。

例如：当前的节点为 u，它的从左至右子节点依次为 v_1, v_2, v_3 时，此时我们可以知道它的前序遍历结果为：

[u, v_1, \textit{children}(v_1), v_2, \textit{children}(v_2), v_3, \textit{children}(v_3)]

后序遍历结果为:

[\textit{children}(v_1), v_1, \textit{children}(v_2), v_2, \textit{children}(v_3), v_3, u]

其中 children}(v_k) 表示以 v_k 为根节点的子树的遍历结果（不包括 v_k）。仔细观察可以知道，将前序遍历中子树的访问顺序改为从右向左可以得到如下访问顺序：

[u, v_3, \textit{children}(v_3), v_2, \textit{children}(v_2), v_1, \textit{children}(v_1)]

将上述的结果进行反转，得到:

[\textit{children}(v_1), v_1, \textit{children}(v_2), v_2, \textit{children}(v_3), v_3, u]

刚好与后续遍历的结果相同。此时我们可以利用前序遍历，只不过前序遍历中对子节点的遍历顺序是从左向右，而这里是从右向左。因此我们可以使用和 N 叉树的前序遍历相同的方法，使用一个栈来得到后序遍历。

我们首先把根节点入栈。当每次我们从栈顶取出一个节点 u 时，就把 u 的所有子节点顺序推入栈中。例如 u 的子节点从左到右为 v_1, v_2, v_3，那么推入栈的顺序应当为 v_1, v_2, v_3，这样就保证了出栈顺序是从右向左，下一个遍历到的节点（即 u 的右侧第一个子节点 v_3）出现在栈顶的位置。在遍历结束之后，我们把遍历结果进行反转，就可以得到后序遍历。

代码

[sol4-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            for (Node item : node.children) {
                stack.push(item);
            }
        }
        Collections.reverse(res);
        return res;
    }
}
[sol4-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<Node *> st;
        st.emplace(root);
        while (!st.empty()) {
            Node * node = st.top();
            st.pop();
            res.emplace_back(node->val);
            for (auto &item : node->children) {
                st.emplace(item);
            }
        }       
        reverse(res.begin(), res.end()); 
        return res;
    }
};
[sol4-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public IList<int> Postorder(Node root) {
        IList<int> res = new List<int>();
        if (root == null) {
            return res;
        }

        Stack<Node> stack = new Stack<Node>();
        stack.Push(root);
        while (stack.Count > 0) {
            Node node = stack.Pop();
            res.Add(node.val);
            foreach (Node item in node.children) {
                stack.Push(item);
            }
        }
        ((List<int>) res).Reverse();
        return res;
    }
}
[sol4-C]
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
#define MAX_NODE_SIZE 10000

int* postorder(struct Node* root, int* returnSize) {
    if (NULL == root) {
        *returnSize = 0;
        return NULL;
    }
    int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    struct Node ** stack = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);
    int pos = 0, top = 0;  

    stack[top++] = root;
    while (top != 0) {
        struct Node * node = stack[--top];
        res[pos++] = node->val;
        for (int i = 0; i < node->numChildren; i++) {
            stack[top++] = node->children[i];
        }
    }
    free(stack);
    for (int l = 0, r = pos - 1; l < r; l++, r--) {
        int tmp = res[l];
        res[l] = res[r];
        res[r] = tmp;
    }
    *returnSize = pos;
    return res;
}
[sol4-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var postorder = function(root) {
    const res = [];
    if (root == null) {
        return res;
    }

    const stack = [];
    stack.push(root);
    while (stack.length) {
        const node = stack.pop();
        res.push(node.val);
        for (const item of node.children) {
            stack.push(item);
        }
    }
    res.reverse();
    return res;
};
[sol4-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        ans = []
        st = [root]
        while st:
            node = st.pop()
            ans.append(node.val)
            st.extend(node.children)
        ans.reverse()
        return ans
[sol4-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func postorder(root *Node) (ans []int) {
    if root == nil {
        return
    }
    st := []*Node{root}
    for len(st) > 0 {
        node := st[len(st)-1]
        st = st[:len(st)-1]
        ans = append(ans, node.Val)
        st = append(st, node.Children...)
    }
    for i, n := 0, len(ans); i < n/2; i++ {
        ans[i], ans[n-1-i] = ans[n-1-i], ans[i]
    }
    return
}

复杂度分析

  • 时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被访问一次。

  • 空间复杂度：O(m)，其中 m 为 N 叉树的节点。如果 N 叉树的深度为 1 则此时栈的空间为 O(1)，如果 N 叉树的深度为 1 则此时栈的空间为 O(m-1)，平均情况下栈的空间为 O(\log m)，因此空间复杂度为 O(m)。

 Comments
On this page
0590-N 叉树的后序遍历