ch7-of-programmercarl-2

C++ C 代码随想录 二叉树 DFS BFS
刷题
发布日期:   2022-04-19

1 路径总和

1.1 题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例1:

输入: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出: true

示例2:

输入: root = [1,2,3], targetSum = 5
输出: false

示例3:

输入: root = [], targetSum = 0
输出: false

1.2 思路

  • DFS: 结束循环的条件是找到叶节点或当前结点为NULL，而找到叶节点的条件为root && !root->left && !root->right为true。DFS也可以转为前序遍历。

  • BFS: 需要创建多余的队列来存储当前层的路径和，没有DFS方便。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    bool flag;
    void dfs(TreeNode* root, int sum, int target){
        if(!root || (root && !root->left && !root->right) || flag){
            if(flag) return;
            if(root && sum+root->val == target){
                flag = true;
            }
            return;
        }else{
            dfs(root->left, sum + root->val, target);
            dfs(root->right, sum + root->val, target);
        }
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        flag = false;
        dfs(root, 0, targetSum);
        return flag;
    }
};
  • C 实现
bool hasPathSum(struct TreeNode* root, int targetSum){
    if(!root) return false;

    int sum = 0;
    struct TreeNode *stack[5001], *cur = root;
    int sums[5001], stack_top = 0;
    while(cur || stack_top != 0){
        while(cur){
            sum += cur->val;
            stack[stack_top] = cur;
            sums[stack_top++] = sum;
            cur =cur->left;
        }
        cur = stack[--stack_top];
        sum = sums[stack_top];
        if(!cur->left && !cur->right && sum == targetSum) return true;
        cur = cur->right;
    }
    return false;
}

2 从中序与后序遍历序列构造二叉树

2.1 题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例1:

输入: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出: [3,9,20,null,null,15,7]

示例2:

输入: inorder = [-1], postorder = [-1]
输出: [-1]

2.2 思路

  • 递归

  直接模拟即可。后序遍历的顺序是“左-右-根”，根节点在数组的最右边，左子树在前，右子树为左子树与根节点之间；而中序遍历是“左-根-右”，根节点位于数组中间(位置不确定)，左子树和右子树位于根节点两端。因此，容易知道，树的根就是postorder的最后一位，然后在inorder中找到对应的下标i，则inorder中左子树范围为0~i-1,因而左子树结点数位i,右子树为i+1~n-1(n为size),数量为n-1-i;由于不同遍历对树的左右子树结点数不影响，因而postorder中左子树的范围同样为0-i-1, 右子树为i~n-2.这样就把树的创建分为根节点-找左子树范围与右子树范围-进入下一层循环。

  上述的过程是第一层循环，而往后的循环其区间不再是0~size-1，而是左右边界均会改变。记inorder中根节点下标为i，左界限为in_left、右界限为in_right(第一层循环y有in_left = 0和in_right = size-1)，postorder中根节点下标为size-1，左界限为post_left、右界限为psot_right(第一层循环y有post_left = 0和post_right = size-1). 进入下一层循环时，构建左子树时有：in_left = in_left, in_right = i-1 和 post_left = post_left, post_right = post_left + i - 1- in_left；右子树时有：in_left = i+1, in_right = in_right 和 post_left = post_left + i- in_left, post_right = post_right-1(按照相对关系和结点数即可得到左右边界).

  • Cpp 实现
class Solution {
public:
    TreeNode* construct(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr){
        if(pl > pr){
            return nullptr;
        }
        TreeNode *root = new TreeNode(postorder[pr]);
        int i;
        for(i = il; i <= ir; ++i){
            if(inorder[i] == postorder[pr]){
                break;
            }
        }
        root->left = construct(inorder, postorder, il, i-1, pl, pl+i-il-1);
        root->right = construct(inorder, postorder, i+1, ir, pl+i-il, pr-1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int size = inorder.size();
        return construct(inorder, postorder, 0, size-1, 0, size-1);
    }   
};

三刷tips: 找索引可以直接用find函数来实现，如通过ii = find(in.begin(), in.end(), post[pr]) - in.begin();来找到中序数组中的分界点，但需要注意，后序数组中的分界点不能通过ip = find(post.begin(), post.end(), in[ii+1]) - post.begin();来实现，因为如果中序数组分界线ii为中序的最后一个，那么前边那个语句中ii+1就会发生越界。应该找完中序数组中的分界线后通过元素个数来进行分治。
这里设第一步中中序分界线元素索引为ii(当前步骤的根节点位置)，那么左子树就是中序数组中的0~ii-1，而右子树是ii+1~size-1，相对应的，后序数组中左子树为0~ii-1,右子树为ii~size-2；而对于整个递归过程，设当前步骤中序数组索引范围为il~ir，而后序则是pl~pr，分界线仍然设为ii，则中序左子树为il~ii-1(左子树节点数为n=ii-1-il+1=ii-il)、右子树为ii+1~ir，而后序左子树为pl~pl+n、右子树为pl+n+1~pr-1.

  • C 实现
struct TreeNode* construct(int* inorder, int* postorder, int size){
    if(size == 0){
        return NULL;
    }
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = postorder[size-1];
    //if(size == 1) return node;
    int pos = 0;
    for(; pos < size; pos++){
        if(inorder[pos] == postorder[size-1]){
            break;
        }
    }
    node->left = construct(inorder, postorder, pos);
    node->right = construct(inorder + (pos+1), postorder + pos, size-pos-1);

    return node;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    return construct(inorder, postorder, inorderSize);
}

C实现中直接通过修改数组的偏置来作为左边界，右边界则是通过结点数和左边界得到，因而传入的变量只需要两个数组(加了偏置)和子树的结点数量即可。

  • 迭代

  后序遍历中，根节点为数组中最后一个数，然后前边的分成左子树和右子树两个部分。由于后序遍历的顺序为“左-右-根”，因而右子树部分中靠后部分其实就是根节点的右孩子；而中序遍历中，数组最后的部分同样也为右孩子，当右子树中的结点都没有左孩子时，那么后序遍历的右子树部分将于中序遍历中对应的部分呈现相反的方向，即中序遍历为从上往下，而后序遍历则是从下往上。当右子树中的结点有左孩子时，中序遍历中左孩子将位于其双亲结点的左侧，即将其双亲结点与其“祖宗”结点们隔开，而后序遍历中仍然保持数组最后一部分为根节点的右孩子、根节点的右孩子的右孩子…(根节点右系)。见下图图解。

  按照后序遍历数组自后而前创建二叉树，先是一直创建右系直至右系创建完成，如何检测创建完成与否呢？创建完成即创建完右系中最后一个结点，即二叉树中最右侧的结点，而这个结点正好为中序遍历数组中的最后一个数，因而只需判断当前结点的值是否等于中序遍历最后的数；右系创建完成后，我们需要在右系的基础上把其余部分添加到上边，这时候就得用到前边提到的“如果右子树中的结点没有左孩子时中序和后序是相反”这个性质，自中序从后而前遍历，当遍历到的数字还没有创建时，说明该数字为某个结点的左孩子，那么其双亲结点如何确定呢？双亲结点其实就是它在inorder中的右侧挨着它的那个数。

  为实现以上思路，需要用一个栈，将已经创建完成的但还没顾及左孩子的结点入栈，当栈顶结点的值与中序数组中最后一个的值一样时说明右系创建完成，开始解决左孩子结点：用一个指针指向中序数组最后一位，当栈顶结点值等于该指针指向的值时，则该指针向前移动，并将该节点出栈；当检测到二者不同时，说明指针指向的值即为刚出栈的结点的左孩子。

完整代码如下：

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        stack<TreeNode*> stk;
        int n = postorder.size();
        TreeNode *root = new TreeNode(postorder[n-1]);
        stk.push(root);
        int inorderIndex = n - 1;
        for(int postorderIndex = n - 2; postorderIndex >= 0; --postorderIndex){
            TreeNode *cur = stk.top();
            if(cur->val != inorder[inorderIndex]){
                cur->right = new TreeNode(postorder[postorderIndex]);
                stk.push(cur->right);
            }else{
                while(!stk.empty() && stk.top()->val == inorder[inorderIndex]){
                    cur = stk.top();
                    stk.pop();
                    --inorderIndex;
                }
                cur->left = new TreeNode(postorder[postorderIndex]);
                stk.push(cur->left);
            }
        }
        return root;
    }
};

3 最大二叉树

3.1 题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例1:

输入: nums = [3,2,1,6,0,5]
输出: [6,3,5,null,2,0,null,null,1]
解释: 递归调用如下所示：

  • [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    • [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
      • 空数组，无子节点。
        • [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
          • 空数组，无子节点。
          • 只有一个元素，所以子节点是一个值为 1 的节点。
    • [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
      • 只有一个元素，所以子节点是一个值为 0 的节点。
      • 空数组，无子节点。

示例2:

输入: nums = [3,2,1]
输出: [3,null,2,null,1]

3.2 思路

  题目已经给出提示了，用递归做。先遍历整个数组找到最大值则创建结点，然后该节点的左孩子就是下一层循环，左边界为上一层的左边界，右边界为上一层最大值对应的下标，而右孩子的左边界则时最大值下标+1，右边界为上一层的右边界。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    TreeNode* construct(vector<int>& nums, int left, int right){
        if(left >= right) return nullptr;
        int index = left;
        for(int i = left; i < right; ++i){
            if(nums[index] > nums[i]){
                continue;
            }
            index = i;
        }
        TreeNode* root = new TreeNode(nums[index]);
        root->left = construct(nums, left, index);
        root->right = construct(nums, index + 1, right);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size());
    }
};
  • C 实现
struct TreeNode* Traversal(int *nums, int left, int right){
    if(left>=right){
        return NULL;
    }

    int maxIndex = left;
    for(int i = left; i < right; i++){
        if(nums[i] > nums[maxIndex])
        maxIndex = i;
    }
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = nums[maxIndex];
    node->left = Traversal(nums, left, maxIndex);
    node->right = Traversal(nums, maxIndex+1, right);
    return node;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
    return Traversal(nums, 0, numsSize);
}

4 合并二叉树

4.1 题目描述

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例1:

输入: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出: [3,4,5,5,4,null,7]

示例2:

输入: root = [4,2,7,1,3], val = 5
输出: [2,2]

4.2 思路

DFS直接解决。

完整代码如下：

  • Cpp实现
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2)    return nullptr;
        else if(!root1)         return root2;
        else if(!root2)         return root1;

        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};
  • C实现
struct TreeNode* merge(struct TreeNode* root1, struct TreeNode* root2){
    if(!root1 && !root2) return NULL;
    else if(!root1) return root2;
    else if(!root2) return root1;

    root1->val += root2->val;
    root1->left = merge(root1->left, root2->left);
    root1->right = merge(root1->right, root2->right);

    return root1;
}

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    return merge(root1, root2);
}

5 二叉搜索树中的搜索

5.1 题目描述

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例1:

输入: root = [4,2,7,1,3], val = 2
输出: [2,1,3]

示例2:

输入: root = [4,2,7,1,3], val = 5
输出: []

5.2 思路

  • 递归大法好。
  • 按照BST的性质进行搜索。

完整代码如下：

  • Cpp实现
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        //递归
        /*if(!root) return nullptr;

        if(root->val == val) return root;
        TreeNode *ans = searchBST(root->left, val);
        if(!ans) ans = searchBST(root->right, val);
        return ans;*/

        //迭代
        while(root){
            if(root->val == val){
                return root;
            }else if(root->val < val){
                root = root->right;
            }else{
                root = root->left;
            }
        }
        return nullptr;
    }
};
  • C实现
struct TreeNode* searchBST(struct TreeNode* root, int val){
    struct TreeNode *cur = root;
    while(cur){
        if(cur->val == val){
            return cur;
        }else if(cur->val < val){
            cur = cur->right;
        }else{
            cur = cur->left;
        }
    }
    return NULL;
}

6 验证二叉搜索树

6.1 题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例1:

输入: root = [2,1,3]
输出: true

示例2:

输入: root = [5,1,4,null,null,3,6]
输出: false

示例3:

输入:
输出:

6.2 思路

中序遍历二叉树，维护一个最小值，最小值即为上一个遍历的结点的值，当当前结点的值小于等于最小值，说明不是二叉搜索树，返回true。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root || (!root->left && !root->right)) return true;
        stack<TreeNode*> stk;
        stk.emplace(root);
        long long minVal = (long long)INT_MIN - 1;
        while(!stk.empty()){
            TreeNode *cur = stk.top();
            stk.pop();
            if(cur){
                if(cur->right) stk.emplace(cur->right);
                stk.emplace(cur);
                stk.emplace(nullptr);
                if(cur->left) stk.emplace(cur->left);
            }else{
                cur = stk.top();
                stk.pop();
                if(cur->val <= minVal) return false;
                minVal = cur->val;
            }
        }
        return true;
    }
};
  • C 实现
bool isValidBST(struct TreeNode* root){
    if(root==NULL) return true;

    struct TreeNode *stack[10001], *cur;
    int stack_top = 0;
    stack[stack_top++] = root;
    long long minVal = LONG_MIN;
    while(stack_top != 0){
        cur = stack[--stack_top];
        if(cur){
            if(cur->right) stack[stack_top++] = cur->right;

            stack[stack_top++] = cur;
            stack[stack_top++] = NULL;

            if(cur->left) stack[stack_top++] = cur->left;
        }else{
            cur = stack[--stack_top];
            if(cur->val <= minVal) return false;
           minVal = cur->val;
        }
    }
    return true;
}

7 二叉搜索树的最小绝对差

7.1 题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例1:

输入: root = [4,2,6,1,3]
输出: 1

示例2:

输入: root = [1,0,48,null,null,12,49]
输出: 1

7.2 思路

二叉搜索树中任意两个节点的值差的绝对值最小必定是两个相邻的结点(或者是左子树中最右端结点与根节点之间)，直接通过中序遍历确定上一个结点的值，然后将当前遍历的节点值与上一个节点值做差并于答案作比较，然后用当前节点值更新上一个节点值，循环遍历整棵树即可。这里有一个小tips，由于都是整数，那么最小差大于等于1，所以当检测到答案为1时就直接返回即可。

完整代码如下：

  • Cpp实现
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> stk;
        int ans = INT_MAX, lastVal = -1;
        stk.emplace(root);
        while(!stk.empty()){
            TreeNode* cur = stk.top();
            stk.pop();
            if(cur){
                if(cur->right) stk.emplace(cur->right);
                stk.emplace(cur);
                stk.emplace(nullptr);
                if(cur->left) stk.emplace(cur->left);
            }else{
                cur = stk.top();
                stk.pop();
                if(lastVal != -1){
                    ans = min(ans, abs(cur->val - lastVal));
                    if(ans == 1) return ans;
                }
                lastVal = cur->val;
            }
        }
        return ans;
    }
};
  • C实现
int getMinimumDifference(struct TreeNode* root){
    struct TreeNode *stack[10001];
    int stack_top = 0;
    stack[stack_top++] = root;
    int prev_val = INT_MAX, ans = INT_MAX;
    while(stack_top!= 0){
        struct TreeNode *cur = stack[--stack_top];
        if(cur){
            if(cur->right) stack[stack_top++] = cur->right;
            stack[stack_top++] = cur;
            stack[stack_top++] = NULL;
            if(cur->left) stack[stack_top++] = cur->left;
        }else{
            cur = stack[--stack_top];
            ans = fmin(ans, abs(cur->val - prev_val));
            prev_val = cur->val;
        }
    }
    return ans;
}

8 二叉搜索树中的众数

8.1 题目描述

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例1:

输入: root = [1,null,2,2]
输出: [2]

示例2:

输入: root = [0]
输出: [0]

8.2 思路

  进行中序遍历，用一个计数器计算当前遍历到的数字出现的次数，并用两个变量分别存放截止至当前出现次数最多的数字和其出现的次数，当检测到当前的数字出现的次数等于最大次数时，就把该数字加入到答案中，如果大于最大次数，则将答案清空并将该数字插入答案，如果遍历到的数字与前一个数字不同时，则将出现次数重置为1.

完整代码如下：

  • Cpp 实现
class Solution {
public: 
    vector<int> ans;
    int cnt, maxtimes, preVal;
    void update(int val){
        if(val == preVal){
            ++cnt;
        }else{
            cnt = 1;
            preVal = val;
        }
        if(cnt == maxtimes){
            ans.emplace_back(val);
        }else if(cnt > maxtimes){
            maxtimes = cnt;
            ans.clear();
            ans.emplace_back(val);
        }
    }
    void inorderTraversal(TreeNode* root){
        if(!root) return;

        inorderTraversal(root->left);
        update(root->val);
        inorderTraversal(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        cnt = 0;
        maxtimes = 1;
        preVal = root->val;
        inorderTraversal(root);
        return ans;
    }
};
  • C 实现
void dfs(struct TreeNode *root, int *preval, int *Cnt, int *maxCnt, int *returnSize, int *ret){
    if(root == NULL) return;
    
    if(root->left){
        dfs(root->left,preval, Cnt, maxCnt, returnSize, ret);
    }
    if(*preval == INT_MAX){
        *Cnt = 1;
    }else if(*preval == root->val){
        (*Cnt)++;
    }else{
        *Cnt = 1;
    }
    *preval = root->val;

    if(*Cnt > *maxCnt){
        *maxCnt = *Cnt;
        *returnSize = 0;
        ret[(*returnSize)++] = root->val;
    }else if(*Cnt == *maxCnt){
        ret[(*returnSize)++] = root->val;
    }
    if(root->right){
        dfs(root->right, preval, Cnt, maxCnt, returnSize, ret);
    }
}
int* findMode(struct TreeNode* root, int* returnSize){
    int *ret = (int *)malloc(sizeof(int) * 10001);
    memset(ret, 0, sizeof(ret));
    *returnSize = 0;
    int preval = INT_MAX;
    int maxCnt  = 0;
    int cnt = 0;
    dfs(root, &preval, &cnt, &maxCnt, returnSize, ret);
    return ret;
}

9 二叉树的最近公共祖先

9.1 题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3

示例2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5

示例3:

输入: root = [1,2], p = 1, q = 2
输出: 1

9.2 思路

  DFS搜索两个结点在树中的位置，如果一个在左一个在右则直接返回根节点，若在同一个子树中，则在那个子树中进行进一步的搜索。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    bool isExist(TreeNode* root, TreeNode* node){
        if(!root) return false;
        if(root->val == node->val) return true;
        return isExist(root->left, node) || isExist(root->right, node);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p|| root == q) return root;
        
        if(isExist(root->left, p) && isExist(root->left, q)){
            return lowestCommonAncestor(root->left, p, q);
        }else if(isExist(root->right, p) && isExist(root->right, q)){
            return lowestCommonAncestor(root->right, p, q);
        }
        return root;
    }
};
  • C 实现
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == p || root == q || root == NULL) return root;

    struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode *right = lowestCommonAncestor(root->right, p, q);
    if(left && right) return root;

    if(!left) return right;
    return left;
}

10 二叉搜索树的最近公共祖先

10.1 题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6

示例2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2

10.2 思路

  • DFS 大法好，如果两个结点的值在root的同一侧则进入下一层递归，传入的结点为两个结点所在的那棵子树。
  • 迭代思路类似，在同一侧则root往那一侧走，不同侧就直接返回root.

完整代码如下：

  • Cpp实现
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val < q->val && root->val < p->val){
            return lowestCommonAncestor(root->right, p, q);
        }else if(root->val > q->val && root->val > p->val){
            return lowestCommonAncestor(root->left, p, q);
        }
        return root;
    }
};
  • C实现
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode *cur = root;
    while(cur!=NULL){
        if(p->val < cur->val && q->val < cur->val){   //在左侧
            cur = cur->left;
        }else if(p->val > cur->val && q->val > cur->val){   //在右侧
            cur = cur->right;
        }else{
            break;
        }
    }
    return cur;
}

总结

文章作者: Vyron Su
文章链接: http://example.com/2022/04/19/ch7-of-programmercarl-2/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vyron Su !
C++ C 代码随想录 二叉树 DFS BFS