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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        stack<TreeNode*> Node;
        int commen = -1;
        bool isFind = false;
        while (root != nullptr || !Node.empty()) {
            while (root != nullptr && root->val != o1 && root->val != o2) {
                Node.push(root);
                if (root->left != nullptr)
                    root = root->left;
                else
                    root = root->right;
            }
            if (root != nullptr) {
                isFind = true;
                if (root->val == o1)
                    commen = o2;
                else
                    commen = o1;
                break;
            }
            root = Node.top();
            Node.pop();
            while (!Node.empty() && (root == Node.top()->right ||
                                     Node.top()->right == nullptr)) {
                root = Node.top();
                Node.pop();
            }
            if (!Node.empty() && root == Node.top()->left)
                root = Node.top()->right;
            else
                root = nullptr;
        }
        cout << root->val << endl;
        Node.push(root);
        isFind = false;
        stack<TreeNode*> Node2;
        while (root != nullptr || !Node.empty()) {
            while (root != nullptr || !Node2.empty()) {
                while (root != nullptr && root->val != commen) {
                    Node2.push(root);
                    cout << root->val << endl;
                    if (root->left != nullptr)
                        root = root->left;
                    else
                        root = root->right;
                }
                if (root != nullptr)
                    return Node.top()->val;
                root = Node2.top();
                Node2.pop();
                while (!Node2.empty() && (Node2.top()->right == nullptr ||
                                          root == Node2.top()->right)) {
                    root = Node2.top();
                    Node2.pop();
                }
                if (!Node2.empty() && root == Node2.top()->left)
                    root = Node2.top()->right;
                else
                    root = nullptr;
            }
            root = Node.top();
            Node.pop();
            while (Node.top()->right == nullptr || Node.top()->right == root) {
                root = Node.top();
                Node.pop();
            }
            if (!Node.empty() && root == Node.top()->left)
                root = Node.top()->right;
            else
                root = nullptr;
        }
        return -1;
    }
};

迭代方法还是用的后序遍历的思路。先按后序遍历，如果找到一个节点和两个要求结点中的一个一样，则此时栈中存的是找到这个结点的路径。现在创建另一个栈，从这个结点接着往后后序遍历。将这个结点遍历完所有子树，如果没有找到另一个结点，（此时第二个栈Node2为空），则弹出第一个栈的栈顶元素，接着找栈中下一个，再用第二个栈Node2后序遍历，直到找到第二个结点，此时第一个栈的栈顶元素就是这个两个结点的最近公共祖先。