[snap]two sum on tree

two node sum to a target on a binary search tree.

instant

I think there should be a better solution...
The below code, I didn't check it, but I think it is correct...

package snapchat;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * Created by kangyue on 1/8/17.
 */

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    
    TreeNode(){
        this.val = val;
    }
}
public class TwoSumTree {
    
    public boolean sumToTarget(TreeNode root, int target){

        Set<Integer> set = new HashSet<>();
        Stack<TreeNode> st = new Stack<>();
        
        TreeNode cur = root;
        
        
        while(!st.isEmpty() || cur != null){
            while(cur != null){
                st.push(cur);
                cur = cur.left;
                
            }
            
            cur = st.pop();
            
            if(set.contains(target - cur.val))return true;
            set.add(cur.val);
            
            cur = cur.right;
        }
        
        return false;
        
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,349评论 0 33
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 13,404评论 0 23
  • 晓来清风残月离,对镜独梳妆 。今非昔比来日茫,玄鬓生白霜。 一夜珠泪草色新,陌上熏花香。山峰压船星河广,无穷无尽流...
    翦梦阅读 2,929评论 40 37
  • 没错,我观剧小能手绝非浪得虚名,今天我又回来啦。 最近在各大社交媒体上被黑得最惨的无非两个剧——《遇见爱情的利先生...
    吹呀吹泡泡阅读 4,668评论 0 51
  • 又是一场深夜! 在被灼热的空气包裹的某个日子里,耳边忽然惊现了蝉鸣,聒噪之后又骤然收紧,但依然让我对这个夏日的接受...
    仪轩阅读 1,917评论 0 1