迭代优化法解决问题实例

迭代优化的思路：

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

参考方法二的原理，可以提前将后续需要访问的节点压入栈中。首先把根节点入栈，因为根节点是前序遍历中的第一个节点。随后每次我们找到栈顶节点 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 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;
}

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