题目地址:https://leetcode.com/problems/cousins-in-binary-tree/

题目描述

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

Twonodes of a binary tree are cousins if they have the same depth, but have different parents.

Weare 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

Note:

1、 Thenumberofnodesinthetreewillbebetween2and100.;
2、 Eachnodehasauniqueintegervaluefrom1to100.;

题目大意

如果一个二叉树中的两个节点的父亲不同,但是高度相同,那么这两个节点是堂兄弟。判断给出的两个值为x和y的节点是不是堂兄弟。

解题方法

DFS

如果做过987. Vertical Order Traversal of a Binary Treeopen in new window,那么这个题肯定很快就能写出来。

题目要求的判断条件有两个1.父节点不同,2.高度相同,所以最直白的方法就是把每个节点的父节点和高度都求出来,然后判断x和y这两个节点是不是符合要求即可。

这个题中每个节点的值都不会重复,所以可以直接用值当做key来存储,代码很简单。

python代码如下:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isCousins(self, root, x, y):
        """
        :type root: TreeNode
        :type x: int
        :type y: int
        :rtype: bool
        """
        self.m = collections.defaultdict(tuple)
        self.dfs(root, None, 0)
        px, dx = self.m[x]
        py, dy = self.m[y]
        return dx == dy and px != py
    
    def dfs(self, root, parent, depth):
        if not root: return
        self.m[root.val] = (parent, depth)
        self.dfs(root.left, root, depth + 1)
        self.dfs(root.right, root, depth + 1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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:
    bool isCousins(TreeNode* root, int x, int y) {
        m_.clear();
        dfs(root, nullptr, 0);
        auto px = m_[x], py = m_[y];
        return px.first != py.first && px.second == py.second;
    }
private:
    unordered_map<int, pair<TreeNode*, int>> m_;
    void dfs(TreeNode* root, TreeNode* parent, int depth) {
        if (!root) return;
        m_[root->val] = make_pair(parent, depth);
        dfs(root->left, root, depth + 1);
        dfs(root->right, root, depth + 1);
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

BFS

相似的,BFS也可以做,不过更简单一点的是不用在队列里保存每个节点的高度了,因为在BFS中搜完每一层才向下一层搜索,所以可以很方便的计算每个节点的高度。

Python代码如下:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isCousins(self, root, x, y):
        """
        :type root: TreeNode
        :type x: int
        :type y: int
        :rtype: bool
        """
        m = collections.defaultdict(tuple)
        q = collections.deque()
        q.append((root, None))
        depth = 0
        while q:
            size = len(q)
            for i in range(size):
                node, p = q.popleft()
                if not node: continue
                m[node.val] = (p, depth)
                q.append((node.left, node))
                q.append((node.right, node))
            depth += 1
        px, dx = m[x]
        py, dy = m[y]
        return dx == dy and px != py

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

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:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<pair<TreeNode*, TreeNode*>> q;
        q.push(make_pair(root, nullptr));
        unordered_map<int, pair<TreeNode*, int>> m_;
        int depth = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto p = q.front(); q.pop();
                if (!p.first) continue;
                m_[p.first->val] = make_pair(p.second, depth);
                q.push(make_pair(p.first->left, p.first));
                q.push(make_pair(p.first->right, p.first));
            }
            ++depth;
        }
        auto px = m_[x], py = m_[y];
        return px.first != py.first && px.second == py.second;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发