D76 993. Cousins in Binary Tree
题目链接
题目分析
在二叉树中,若两个叶子节点的层数相同,但具有不同的父节点,那么这两个节点互为cousin节点。
给定一个二叉树及x、y两个节点,返回x、y两个节点在二叉树中,是否互为cousin节点。
思路
因为x和y在二叉树中唯一,故我们可已先遍历整个二叉树,把当前节点的值作为数组的键,把当前的层数作为值,存进一个数组中。
遍历完成后,直接判断数组中对应的值是否相同即可。
最终代码
<?php
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @param Integer $x
* @param Integer $y
* @return Boolean
*/
public $data = [];
public $level = [];
function isCousins($root, $x, $y) {
$this->inOrder($root, 0, 0);
return ($this->prnt[$x] != $this->prnt[$y]) && ($this->level[$x] == $this->level[$y]);
}
function inOrder($root, $crnt, $level){
if(is_null($root)){
return;
}
$this->prnt[$root->val] = $crnt;
$this->level[$root->val] = $level;
$level++;
$this->inOrder($root->left, $root->val, $level);
$this->inOrder($root->right, $root->val, $level);
}
}
若觉得本文章对你有用,欢迎用爱发电资助。
网友评论