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

注前序遍历+栈思想

/**
 * 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

        if(!root){
            return 0;
        }


        int result;

        vector<int> o1_path;
        vector<int> o2_path;

        vector<int> path;

        int finish = 0;
        preorder(root, o1_path,o1,finish,path);
        path.clear();
        finish = 0;
        preorder(root, o2_path,o2,finish,path);

        int min_length;


        if(o1_path.size()<=o2_path.si***_length = o1_path.size();
        }else{
            min_length = o2_path.size();
        }

        for(int i = 0; i< min_length;i++){
            if(o1_path[i]==o2_path[i]){
                result = o1_path[i];
            }
        }


        return result;
    }

    void preorder(TreeNode* root, vector<int>& result, int target, int &finish, vector<int>& path ){

        if(!root || finish){
            return;
        }

        path.push_back(root->val);

        if(root->val == target){
           finish = 1;
           result = path;
        }

        preorder(root->left, result, target, finish,path);
        preorder(root->right,result, target,finish,path);

        path.pop_back();

    }

};