原文链接 [每日 LeetCode] 993. Cousins in Binary Tree Description In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1. Tw ..

[每日 LeetCode] 993. Cousins in Binary Tree

本贴最后更新于 289 天前,其中的信息可能已经天翻地覆

原文链接 [每日 LeetCode] 993. Cousins in Binary Tree

Description

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are_cousins_if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

思路:本题的意思为:定义二叉树中的“堂兄弟”结点,即两个深度相同且父结点不同的结点。给定一棵结点值互异的二叉树和两个树中的结点值 xy ,问这两个结点是否为堂兄弟。只要遍历二叉树,并记录对应的两个结点的父节点和深度即可。遍历时注意以下三点:

这是第二个代码跑出了 0ms。超过了 100% 的提交。


C++ 代码

/**
 * 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:
    int x_depth,y_depth,x_parent,y_parent;
    bool isCousins(TreeNode* root, int x, int y) {
        isCousins_sub(root,x,y,0,root->val);
        if ((x_depth == y_depth) && (x_parent != y_parent))
            return true;
        else
            return false;
    }
    void isCousins_sub(TreeNode* root, int x, int y, int depth,int parent) {
        if(!root) return;
        depth++;
        if(root->val == x){
            x_depth = depth;
            x_parent = parent;
        }
        else if(root->val == y){
            y_depth = depth;
            y_parent = parent;
        }
        else{
            isCousins_sub(root->left,x,y,depth,root->val);
            isCousins_sub(root->right,x,y,depth,root->val);
        }
    }
};

运行时间:0ms

运行内存:11.4M

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    164 引用 • 61 回帖
  • Tree
    35 引用 • 6 回帖
  • Easy
    101 引用 • 10 回帖
回帖
请输入回帖内容...