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

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

https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

class Solution {
  private:
    TreeNode* Preoder(TreeNode* root, int o1, int o2) {
        if (root == nullptr || root->val == o1 || root->val == o2) {
            return root;
        }

        TreeNode* leftResult = Preoder(root->left, o1, o2);
        TreeNode* rightResult = Preoder(root->right, o1, o2);
        if (leftResult != nullptr && rightResult != nullptr) {
            return root;
        } else if (leftResult != nullptr && rightResult == nullptr) {
            return leftResult;
        } else if (leftResult == nullptr && rightResult != nullptr) {
            return rightResult;
        }
        return nullptr;
    }

  public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // 本题保证非空
        TreeNode* result = Preoder(root, o1, o2);
        return result->val;
        }
};

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务