利用递归来遍历树

利用递归来遍历树，实际的递归中隐式利用了栈，在此我们可以直接模拟递归中栈的调用。在后序遍历中从左向右依次先序遍历该每个以子节点为根的子树，然后先遍历节点本身。在这里的栈模拟中比较难处理的在于从当前节点 u 的子节点 v1 返回时，此时需要处理节点 u 的下一个节点 v2 ，此时需要记录当前已经遍历完成哪些子节点，才能找到下一个需要遍历的节点。在二叉树树中因为只有左右两个子节点，因此比较方便处理，在 N 叉树中由于有多个子节点，因此使用哈希表记录当前节点 u 已经访问过哪些子节点。

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

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

代码

Java

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;}
}

C++

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;}
};

C#

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;}
}     

好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！