C++/Python Straight Forward Solution


  • 9

    In my solution, I check the target value during the search, whick makes the solution conciser.

    C++:

    class Solution {
        set<int> s;
        bool dfs(TreeNode *cur, int k) {
            if (!cur) return false;
            if (s.count(k - cur->val)) return true;
            s.insert(cur->val);
            return dfs(cur->left, k) || dfs(cur->right, k);
        }
    public:
        bool findTarget(TreeNode* root, int k) {
            s.clear();
            return dfs(root, k);
        }
    };
    

    Python:

    def findTarget(self, root, k):
            if not root: return False
            bfs, s = [root], set()
            for i in bfs:
                if k - i.val in s: return True
                s.add(i.val)
                if i.left: bfs.append(i.left)
                if i.right: bfs.append(i.right)
            return False

  • 0
    Z

    why you use list in python solution rather than set?


  • 1

    @zqfan
    In C++, I used recursive dfs.
    In Python, I used a list for iterative bfs.


  • 1
    T

    brilliant solution


  • 0
    W

    @lee215 Hello.i am confuse why
    ~~
    if i.left: bfs.append(i.left)
    if i.right: bfs.append(i.right)
    ~~
    can anyone explain this ?
    thanks!


  • 0
    W

    @WJFQQQ said in C++/Python Straight Forward Solution:

    @lee215 Hello.i am confuse why

            if i.left: bfs.append(i.left)
            if i.right: bfs.append(i.right)
    

    in python solution

    can anyone explain this ?
    thanks!


  • 0

    @WJFQQQ
    bfs is a list of nodes to search.

     if i.left: bfs.append(i.left)
    

    if the current node has a left child, add this child node to the list and it will be parsed later. The same for right child.


  • 0
    L

    Why does bfs = [root] creat a list of nodes to search? Is this specified in the node class?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.