题解 | #在二叉树中找到两个节点的最近公共祖先#

后序遍历，非递归实现

vector<int> postorder(Node* root,int target) {
    vector<Node*> st={};
    Node* current=root;
    Node* prior=nullptr;
    while(current || !st.empty()) {
        while(current) {
            st.push_back(current);
            current=current->left;
        }
        if(!st.empty()) {
            current=st.back();
            // visit(current);
            if(current->val==target) {
                vector<int> path={};
                for(auto np:st) {
                    path.push_back(np->val);
                }
                return path;
            }
            st.pop_back();
            if(!current->right || prior==current->right) {
                prior=current;
                current=nullptr;
            } else {
                st.push_back(current);
                current=current->right;
            }
        }
    }
    return {};
}

int prefixCompare(Node* root, int val1, int val2) {
    auto path1=postorder(root,val1);
    auto path2=postorder(root,val2);
    int ans=-1;
    for (int i = 0; i < path1.size() && i <  path2.size(); i++){
        int x=path1[i];
        int y=path2[i];
        if(x==y) ans=x;
    }
    if(ans==-1) return -1;
    return ans;
}

后序遍历基于栈实现，关键在于遍历到目标节点时栈中存储的恰好是起于根节点的路径。