lowest_common_ancestor_binary_tree

2022-12-14
浏览 (507)

lowest_common_ancestor_binary_tree.cpp 源码

// 二叉树的最近公共祖先

#include "stack"
#include "queue"
using namespace std;

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

    TreeNode() {}
    TreeNode(int val) : val(val) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

class Solution {
public:

    // 如果 root 为空，或者 p q 任意一个等于 root，则直接返回
    // 递归遍历左右
    // 如果左右均不为空，则说明root就是最近公共祖先
    // 否则哪个不为空就返回哪个
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) {
            return root;
        }
        return left == nullptr ? right : left;
    }
};

你可能感兴趣的文章

binary_tree_inorder

binary_tree_level_order

binary_tree_level_order_ii

0 赞

所属分类： 后端技术
本文标签： 技术
版权声明： 原创文章如转载，请注明本文链接: https://www.seaxiang.com/blog/1067d39620ea401095be4ac7a3a32fcb

热门推荐

1、直接访问google.com
2、 - 优质文章
3、 gate.io
4、 harmony 鸿蒙hdc使用指导
5、 harmony 鸿蒙初识ArkTS语言
6、 harmony 鸿蒙ArkUI组件（ArkTS）开发常见问题
7、 flink kafka connector scan.startup.mode 的几个选项
8、 golang
9、 openharmony
10、 Vue中input框自动聚焦

Loading...