2-Sum Binary Tree

题目描述

要求linear time, memory no more than O(height of T)

解题方法

brute force

比较每个pair O(n^2)

inorder -> sorted array

inorder生成sorted array后就可以用2 sum的方法了，但是需要O(n)的space

optimized solution

Convert given BST to doubly linked list
然后在list里找到pair需要o(n)
space complexity 是O(logn)

但是这个方法需要修改原来的BST

另一种不用修改BST的方法！

用一个正常的in-order traversal和一个reverse的in-order traversal来模拟sorted array中寻找2 sum时一个start pointer和一个end pointer的.

两个traversal当pop出一个value的时候就要停下来比较，如果不满足再根据大小调节哪一个“指针”需要移动。

Solution

两个in-order traversal的方法

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

class Solution:
    # @param A : root node of tree
    # @param B : integer
    # @return an integer
    def t2Sum(self, A, B):
        s1 = [] # normal in-order
        s2 = [] # reverse in-order, right subtree first
        done1, done2 = False, False
        curr1, curr2 = A, A
        while True:
            # normal in-order traversal
            while done1 == False:
                if curr1:
                    s1.append(curr1)
                    curr1 = curr1.left
                else:
                    if not s1:
                        done1 = True
                    else:
                        # find first one, then exist for compare
                        node1 = s1.pop()
                        val1 = node1.val
                        curr1 = node1.right
                        done1 = True
            # reverse in-order traversal
            while done2 == False:
                if curr2:
                    s2.append(curr2)
                    curr2 = curr2.right
                else:
                    if not s2:
                        done2 = True
                    else:
                        node2 = s2.pop()
                        val2 = node2.val
                        curr2 = node2.left
                        done2 = True
            # 有两个值了就出来比较
            if val1 != val2 and val1 + val2 == B:
                return 1
            elif val1 + val2 > B:
                done2 = False
            elif val1 + val2 < B:
                done1 = False
            # 跨过中点了还是没有找到，就可以return了
            if val1 >= val2:
                return 0

questions_review