Ссылка на Заголовок
993. Двоюродные братья в двоичном дереве
Анализ названия
В двоичном дереве, если количество слоев двух конечных узлов одинаково, но у них разные родительские узлы, то эти два узла являются двоюродными узлами.
Учитывая двоичное дерево и два узла X и y, верните, являются ли два узла X и y двоичными узлами в двоичном дереве.
размышляющий
Поскольку 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);
}
}Если вы считаете, что эта статья полезна для вас, вы можете воспользоваться Фондом генерации энергии Ии.