首页 > 其他 > 详细

leetcode 关于树的题目

时间:2018-07-08 17:38:48      阅读:193      评论:0      收藏:0      [点我收藏+]

判断一棵树里是否有两个节点的值之和等于某个值。

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   /   3   6
 / \   2   4   7

Target = 9

Output: True

 

Example 2:

Input: 
    5
   /   3   6
 / \   2   4   7

Target = 28

Output: False
思路:使用 unordered_set存储??节点的值。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_set<int> s;
    bool dfs(TreeNode* root,int k, unordered_set<int>& s){
        if(root==nullptr) return false;
        if(s.count(k-root->val)) return true;
        s.insert(root->val);
        return dfs(root->left,k,s)||dfs(root->right,k,s);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        s.clear();
        return dfs(root,k,s);
    }
};

 python代码

创建集合 set(), 插入 add (c++ insert)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def helper(self,root,k,s):
        if not root:
            return False
        if k-root.val in s:
            return True
        s.add(root.val)
        return self.helper(root.left,k,s) or self.helper(root.right,k,s)
    
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        s=set()
        return self.helper(root,k,s)
        
        

 

leetcode 关于树的题目

原文:https://www.cnblogs.com/learning-c/p/9280596.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!