Leetcode PHP题解--D89 653. Two Sum IV - Input is a BST

D89 653. Two Sum IV - Input is a BST

题目链接

653. Two Sum IV - Input is a BST

题目分析

给定一个二叉树以及一个目标数字，判断能不能通过二叉树中任意两个节点的值相加得到。

思路

思路1

遍历的时候，先把节点存起来，并且与每一个值相加，判断是否等于所需值。

这个算法很明显效率比较低。

思路2

遍历的时候，把自身作为键存进数组内。用isset函数判断与所求数字之差是否在数组内。存在既返回。否则，遍历子节点。

最终代码

<?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 {
    protected $has = [];
        protected $hasResult = false;
            /**
                 * @param TreeNode $root
                      * @param Integer $k
                           * @return Boolean
                                */
                                    function findTarget($root, $k) {
                                            if(is_null($root)){
                                                        return;
                                                                }
                                                                        if(isset($this->has[$k-($root->val)])){
                                                                                    $this->hasResult = true;
                                                                                                return $this->hasResult;
                                                                                                        }
                                                                                                                else{
                                                                                                                            $this->has[$root->val] = true;
                                                                                                                                        if(!$this->findTarget($root->left, $k)){
                                                                                                                                                        $this->findTarget($root->right, $k);
                                                                                                                                                                    }
                                                                                                                                                                            }
                                                                                                                                                                                    return $this->hasResult;
                                                                                                                                                                                        }
                                                                                                                                                                                        }

若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。