网站建设技术架构和语言,农业网站设计,wordpress添加tag标签,专业的医疗行业网站模板给定一个二叉搜索树 root 和一个目标结果 k#xff0c;如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果#xff0c;则返回 true。 输入: root [5,3,6,2,4,null,7], k 9
输出: true 1.第一种思路
中序遍历双指针
即先中序递归遍历并用动态数组ArrayList存储如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果则返回 true。 输入: root [5,3,6,2,4,null,7], k 9
输出: true 1.第一种思路
中序遍历双指针
即先中序递归遍历并用动态数组ArrayList存储会得到一个升序数组再通过双指针让两个指针分别指向数组的两头再求和比较若和大于目标数右指针左移若和小于目标数右指针左移。
class Solution {public boolean findTarget(TreeNode root, int k) { ArrayList arr new ArrayList();inOrder(root,arr);int left 0; //双指针int right arr.size()-1;while(leftright){if((int)arr.get(left)(int)arr.get(right) k) {right--;}else if((int)arr.get(left)(int)arr.get(right) k) {left;}else{return true;}}return false;}//中序遍历public static void inOrder(TreeNode root,ArrayList arr){if(rootnull) return;inOrder(root.left,arr);arr.add(root.val);inOrder(root.right,arr);}} 2.第二种思路
深度优先搜索哈希表
先深度优先搜索遍历整棵二叉树在遍历的同时在哈希表中存储当前结点的值。
对于一个值为 x 的节点首先检查哈希表中是否存在 k−x 。如果存在对应的元素则遍历结束返回true否则将 x 放入到哈希表中,接着进行往下遍历。如果遍历完整棵树都不存在对应的元素那么该树上不存在两个和为 kkk 的节点。检查哈希表中是否存在 k−x和将值放入到哈希表中是有先后顺序的。
public boolean findTarget(TreeNode root, int k) { SetInteger set new HashSet();if(rootnull) return false;if(set.contains(k-root.val)) return true; //先判断set.add(root.val); //再添加return inOrder(root.left,k) || inOrder(root.right,k); //遍历当前节点的左右子树 } 3.第三种思路
广度优先搜索队列 哈希表
广度优先搜索即层序遍历需要用到队列操作。我用的是非递归每当出队列时用哈希表进行判断和存储。细节和第二种思路是一样的。
//广度优先搜索 队列 哈希表public boolean findTarget(TreeNode root, int k) { SetInteger set new HashSet(); return levelOrder(root,k,set);}//非递归层序遍历public static boolean levelOrder(TreeNode root,int k,SetInteger set) {if(root null) return false;QueueTreeNode queue new LinkedList();//先得加入一个根节点queue.offer(root);while(!queue.isEmpty()) {//出队列TreeNode node queue.poll(); if(!set.contains(k-node.val)) {set.add(node.val);} else {return true;}//左子树存在才加if(node.left!null) queue.offer(node.left);//右子树存在才加if(node.right!null) queue.offer(node.right); } return false;}
