Hello, 大家好，今天是我参加 9 月更文的第 6 天，今天给大家带来的关于二叉树相关的算法题是二叉树的所有路径，正文如下：
题目
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
示例 1：
输入: root = [8,6,10,5,7,9,11], k = 12输出: true解释: 节点 5 和节点 7 之和等于 12
复制代码
示例 2：
输入: root = [8,6,10,5,7,9,11], k = 22输出: false解释: 不存在两个节点值之和为 22 的节点
复制代码
解题思路
根据题意，给出的二叉树是一棵二叉搜索树，首先我们想到的就是可以利用中序排序，得到一个有序数组；
由于要判断是否存在俩个节点的值之和等于 k, 可以让我们联想到俩数之和的解题思路，那就是利用哈希表来保存当前节点的值，而且我们也不只是局限于非要用中序排序来遍历该二叉树，任何形式的遍历都是可取的，每当遍历到一个节点，若 k 减去该节点的值存在于哈希表内，则返回 true, 反之则保存该节点的值到哈希表中，并开始遍历下一个节点。
代码实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public Set<Integer> set = new HashSet(); public boolean findTarget(TreeNode root, int k) { if (root == null) { return false; } // 是否存在哈希表中 if (set.contains(k - root.val)) { return true; } // 反之则加入到哈希表中 set.add(root.val); // 继续遍历 return findTarget(root.left, k) || findTarget(root.right, k); }}
复制代码
最后
复杂度分析：
时间复杂度为 O(n)：由于二叉树的节点数为 n ,所以时间复杂度为 O(n);
空间复杂度为 O(n)：由于二叉树的高度为 h, 所以遍历时的栈的空间复杂度为 O(h), 哈希表的空间复杂度为 O(n), 所以总的空间复杂度为 O(n);
评论