【LeetCode】236. Lowest Common Ancestor of a Binary Tree

前言

花了蠻多時間在想解題方法，因為我自己對樹的操作不是那麼熟悉，所以希望可以自己解出來，但最後還是以失敗告終。
我發現這題的方法不只一種，但基本概念都是traversal遍歷整個樹才能得到答案，有迴圈的寫法，也有DFS的寫法，我這次是用DFS。

方法

用DFS遍歷每個節點，紀錄節點的下面有沒有包含目標（p,q），因為是DFS，會跑到最深，得到數字後，才往回回傳，所以第一個遇到下面都包含目標的節點，就一定會是Lowest Common Ancestor。

若不找Lowest，這題就把第一個的判斷拿掉，所有dfs return為2的節點，都會是common ancestor。

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* ret = NULL;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ret;
    }
    int dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        int count = 0;
        if (root){
            if (root->val == p->val || root->val == q->val) count++;
            count += dfs(root->left, p, q);
            count += dfs(root->right, p, q);
            if (count == 2 && ret == NULL){ // ret just want to be changed at first time
                ret = root;
            }
        }
        return count;
    }
};

tags: LeetCode 程式