golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2024-02-08 10:11:17

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x, y int) (ans bool) {
    depth := 0
    var father *TreeNode
    var dfs func(*TreeNode, *TreeNode, int) bool
    dfs = func(node, fa *TreeNode, d int) bool {
        if node == nil {
            return false
        }
        if node.Val == x || node.Val == y { // 找到 x 或 y
            if depth > 0 { // 之前已找到 x y 其中一个
                ans = depth == d && father != fa
                return true // 表示 x 和 y 都找到
            }
            depth, father = d, fa // 之前没找到，记录信息
        }
        return dfs(node.Left, node, d+1) || dfs(node.Right, node, d+1)
    }
    dfs(root, nil, 1)
    return
}

java 解法, 执行用时: 0 ms, 内存消耗: 40.4 MB, 提交时间: 2024-02-08 10:11:00

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private boolean ans;
    private int depth;
    private TreeNode father;

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 1, x, y);
        return ans;
    }

    private boolean dfs(TreeNode node, TreeNode fa, int d, int x, int y) {
        if (node == null) {
            return false;
        }
        if (node.val == x || node.val == y) { // 找到 x 或 y
            if (depth > 0) { // 之前已找到 x y 其中一个
                ans = depth == d && father != fa;
                return true; // 表示 x 和 y 都找到
            }
            depth = d; // 之前没找到，记录信息
            father = fa;
        }
        return dfs(node.left, node, d + 1, x, y) || dfs(node.right, node, d + 1, x, y);
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 13.4 MB, 提交时间: 2024-02-08 10:10:43

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode *root, int x, int y) {
        bool ans = false;
        int depth = 0;
        TreeNode *father = nullptr;
        function<bool(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode *node, TreeNode *fa, int d) -> bool {
            if (node == nullptr) {
                return false;
            }
            if (node->val == x || node->val == y) { // 找到 x 或 y
                if (depth) { // 之前已找到 x y 其中一个
                    ans = depth == d && father != fa;
                    return true; // 表示 x 和 y 都找到
                }
                depth = d; // 之前没找到，记录信息
                father = fa;
            }
            return dfs(node->left, node, d + 1) || dfs(node->right, node, d + 1);
        };
        dfs(root, nullptr, 1);
        return ans;
    }
};

python3 解法, 执行用时: 44 ms, 内存消耗: 16.4 MB, 提交时间: 2024-02-08 10:10:29

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        ans = False
        depth = father = None
        def dfs(node: Optional[TreeNode], fa: Optional[TreeNode], d: int) -> bool:
            if node is None:
                return False
            if node.val == x or node.val == y:  # 找到 x 或 y
                nonlocal ans, depth, father
                if depth:  # 之前找到 x y 其中一个
                    ans = depth == d and father != fa
                    return True  # 表示 x 和 y 都找到
                depth, father = d, fa  # 之前没找到，记录信息
            return dfs(node.left, node, d + 1) or dfs(node.right, node, d + 1)
        dfs(root, None, 1)
        return ans

python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2021-05-17 10:25:18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        # x 的信息
        x_parent, x_depth, x_found = None, None, False
        # y 的信息
        y_parent, y_depth, y_found = None, None, False
        
        def dfs(node: TreeNode, depth: int, parent: TreeNode):
            if not node:
                return
            
            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found
            
            if node.val == x:
                x_parent, x_depth, x_found = parent, depth, True
            elif node.val == y:
                y_parent, y_depth, y_found = parent, depth, True

            # 如果两个节点都找到了，就可以提前退出遍历
            # 即使不提前退出，对最坏情况下的时间复杂度也不会有影响
            if x_found and y_found:
                return

            dfs(node.left, depth + 1, node)

            if x_found and y_found:
                return
            dfs(node.right, depth + 1, node)

        dfs(root, 0, None)
        return x_depth == y_depth and x_parent != y_parent