Leetcode題解 Python & C#：五月挑戰DAY7 Cousins in Binary Tree

給一個二元樹的根節，找出 x、y是否為cousin（同深度，不同父）。

遍歷所有的節，再把找到的x、y資料（深度，父節）做對比，就可以辨別是否為cousin 。

要找遍二元樹上的每一個元素，除了可以用遞迴函數，也可以用一層一層的stack（queue皆可)來找。由於每節的值不會重複，不用擔心多個可能。

就效率來看，這題的情況單純，儘可能減少判斷，才是通往高效之路。

Python

class Solution:
    def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
        
        def search(node, parent, depth, val):
            if not node: return None, None
            if node.val == val:
                return parent, depth
            else:
                res = search(node.left, node, depth+1, val)
                if res[0]: return res
                return search(node.right, node, depth+1, val)
            
        nodeX = search(root, None, 0, x)
        nodeY = search(root, None, 0, y)
        return (nodeX[0] != nodeY[0] and nodeX[1] == nodeY[1])

C#

public class Solution {
    public bool IsCousins(TreeNode root, int x, int y) {
        var queue = new Queue();
        var memo = new Dictionary();
        queue.Enqueue(root);
        memo[root.val] = root;
        while(queue.Count > 0)
        {
            int len = queue.Count;
            for(int i = 0; i < len; i++)
            {
                var node = queue.Dequeue();
                if(!(node.left is null))
                {
                    memo[node.left.val] = node;
                    queue.Enqueue(node.left);
                }   
                if(!(node.right is null))
                {
                    memo[node.right.val] = node;
                    queue.Enqueue(node.right);
                }                   
            }
            var hasX = memo.ContainsKey(x);
            var hasY = memo.ContainsKey(y);
            if(hasX | hasY)
            {
                if(hasX & hasY)
                {
                    if(memo[x] != memo[y])
                        return true;
                    else
                        break;
                }
                else
                {
                    break;
                }
            }
        }
        return false;
    }
}