迭代优化法解决问题实例

迭代优化的思路：

在后序遍历中，我们会先从左向右依次后序遍历每个子节点为根的子树，再遍历根节点本身。此时利用栈先进后出的原理，依次从右向左将子节点入栈，这样出栈的时候即可保证从左向右依次遍历每个子树。

参考方法二的原理，可以提前将后续需要访问的节点压入栈中。首先把根节点入栈，因为根节点是前序遍历中的第一个节点。随后每次我们找到栈顶节点 u ，如果当前节点的子节点没有遍历过，则应该先把 u 的所有子节点从右向左逆序压入栈中，这样出栈的节点则是顺序从左向右的，同时对节点 u 进行标记，表示该节点的子节点已经全部入栈；

如果当前节点 u 为叶子节点或者当前节点的子节点已经全部遍历过，则从栈中弹出节点 u ，并记录节点 u 的值。例如 u 的子节点从左到右为 v1 , v2 , v3 ，那么入栈的顺序应当为 v3, v2 , v1，这样就保证了下一个遍历到的节点（即 u 的左侧第一个孩子节点 v1 ）出现在栈顶的位置。此时，访问第一个子节点 v1 时，仍然按照此方法则会先访问 v1 的左侧第一个孩子节点。

代码

Java

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

C++

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

C#

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

C

#define MAX_NODE_SIZE 10000typedef 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;
}

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