{"id":4855,"date":"2019-02-16T23:08:20","date_gmt":"2019-02-17T07:08:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4855"},"modified":"2019-02-16T23:19:43","modified_gmt":"2019-02-17T07:19:43","slug":"leetcode-993-cousins-in-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-993-cousins-in-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 993. Cousins in Binary Tree"},"content":{"rendered":"\n

In a binary tree, the root node is at depth 0<\/code>, and children of each depth k<\/code> node are at depth k+1<\/code>.<\/p>\n\n\n\n

Two nodes of a binary tree are cousins<\/em> if they have the same depth, but have different parents<\/strong>.<\/p>\n\n\n\n

We are given the root<\/code> of a binary tree with unique values, and the values x<\/code> and y<\/code> of two different nodes in the tree.<\/p>\n\n\n\n

Return true<\/code> if and only if the nodes corresponding to the values x<\/code> and y<\/code> are cousins.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Example 1:
<\/strong><\/p>\n\n\n\n

Input: <\/strong>root = [1,2,3,4], x = 4, y = 3\nOutput: <\/strong>false\n<\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Example 2:
<\/strong><\/p>\n\n\n\n
Input: <\/strong>root = [1,2,3,null,4,null,5], x = 5, y = 4\nOutput: <\/strong>true\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Input: <\/strong>root = [1,2,3,null,4], x = 2, y = 3\nOutput: <\/strong>false<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. The number of nodes in the tree will be between 2<\/code> and 100<\/code>.<\/li>
  2. Each node has a unique integer value from 1<\/code> to 100<\/code>.<\/li><\/ol>\n\n\n\n
    Solution: Preorder traversal<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time 8 ms, 11.5 MB\nclass Solution {\npublic:\n  bool isCousins(TreeNode* root, int x, int y) {    \n    preorder(root, x, y, nullptr, 0);\n    return px_ != py_ && dx_ == dy_;\n  }\nprivate:\n  TreeNode* px_;\n  TreeNode* py_;\n  int dx_;\n  int dy_;\n  \n  void preorder(TreeNode* root, int x, int y, TreeNode* p, int d) {\n    if (!root) return;\n    if (root->val == x) {\n      px_ = p;\n      dx_ = d;\n    }\n    if (root->val == y) {\n      py_ = p;\n      dy_ = d;\n    }\n    preorder(root->left, x, y, root, d + 1);\n    preorder(root->right, x, y, root, d + 1);\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua, running time: 40 ms, 12.4 MB\nclass Solution:\n  def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':\n    self.px, self.dx = None, -1\n    self.py, self.dy = None, -2\n    def preorder(root, parent, d):\n      if not root: return\n      if root.val == x: \n        self.px, self.dx = parent, d\n      if root.val == y:\n        self.py, self.dy = parent, d\n      preorder(root.left, root, d + 1)\n      preorder(root.right, root, d + 1)\n    preorder(root, None, 0)\n    return self.dx == self.dy and self.px != self.py\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[222,28],"class_list":["post-4855","post","type-post","status-publish","format-standard","hentry","category-tree","tag-easy","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4855","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4855"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4855\/revisions"}],"predecessor-version":[{"id":4861,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4855\/revisions\/4861"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4855"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4855"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4855"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}