4

这是我的代码。我正在遍历整个树,然后在每个节点上进行查找。find()需要 O(log n),因此整个程序需要 O(n log n) 时间。

有没有更好的方法来实施这个程序?我不仅在时间复杂度方面谈论更好,而且在一般情况下也是如此。如何最好地实现这一点?

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input

    if (node == null) {
        return false;
    }
    // terminal case for recursion

    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if (find(result)) {
        return true;
    }
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);

}

public boolean find(int key) {

    BinTreeNode node = findHelper(key, root);
    if (node == null) {
        return false;
    } else {
        return true;
    }
}


private BinTreeNode findHelper(int key, BinTreeNode node) {
    if (node == null) {
        return null;
    }
    if (key == node.item) {
        return node;
    } else if (key < node.item) {
        return findHelper(key, node.leftChild);
    } else {
        return findHelper(key, node.rightChild);
    }
}
4

6 回答 6

9

在二叉搜索树中查找两个节点总和为某个值的方法与在排序数组中查找两个总和为该值的元素类似。

在数组从小到大排序的情况下,您保留两个指针,一个从开头开始,一个从结尾开始。如果指针指向的两个元素之和大于目标,则将右指针向左移动一,如果和小于目标,则将左指针向右移动一。最终,两个指针要么指向总和为目标值的两个元素,要么在中间相遇。

boolean searchNumArray(int[] arr, int num) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == num) {
          return true;
        } else if (sum > num) {
          right--;
        } else {
          left++;
        }
    }
    return false;
} 

如果你对二叉搜索树进行中序遍历,它就会变成一个排序数组。所以你可以在二叉搜索树上应用同样的想法。

以下代码从两个方向进行迭代按顺序遍历。堆栈用于遍历,因此时间复杂度为 O(n),空间复杂度为 O(h),其中 h 是二叉树的高度。

class BinTreeIterator implements Iterator<BinTreeNode> {
    Stack<BinTreeNode> stack;
    boolean leftToRight;

    public boolean hasNext() {
        return !stack.empty();
    }

    public BinTreeNode next() {
        return stack.peek();
    }

    public void remove() {
        BinTreeNode node = stack.pop();
        if (leftToRight) {
            node = node.rightChild;
            while (node.rightChild != null) {
                stack.push(node);
                node = node.rightChild;
            }
        } else {
            node = node.leftChild;
            while (node.leftChild != null) {
                stack.push(node);
                node = node.leftChild;
            }
        }
    }

    public BinTreeIterator(BinTreeNode node, boolean leftToRight) {
        stack = new Stack<BinTreeNode>();
        this.leftChildToRight = leftToRight;

        if (leftToRight) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
        } else {
            while (node != null) {
                stack.push(node);
                node = node.rightChild;
            }
        }            
    }
}



public static boolean searchNumBinTree(BinTreeNode node, int num) {
    if (node == null)
        return false;

    BinTreeIterator leftIter = new BinTreeIterator(node, true);
    BinTreeIterator rightIter = new BinTreeIterator(node, false);

    while (leftIter.hasNext() && rightIter.hasNext()) {
        BinTreeNode left = leftIter.next();
        BinTreeNode right = rightIter.next();
        int sum = left.item + right.item;
        if (sum == num) {
            return true;
        } else if (sum > num) {
            rightIter.remove();
            if (!rightIter.hasNext() || rightIter.next() == left) {
                return false;
            }
        } else {
            leftIter.remove();
            if (!leftIter.hasNext() || leftIter.next() == right) {
                return false;
            }
        }
    }

    return false;
}
于 2013-09-20T01:21:22.103 回答
1

陈庞已经给出了完美的答案。但是,我今天尝试了同样的问题,我可以提出以下解决方案。把它贴在这里,因为它可能会帮助一些人。

这个想法与早期解决方案的想法相同,只是我用两个堆栈来做 - 一个在 inorder(stack1) 之后,另一个在反向之后 - inorder order(stack2)。一旦我们到达 BST 中最左边和最右边的节点,我们就可以开始将它们一起比较。

如果总和小于所需值,则从 stack1 中弹出,否则从 stack2 中弹出。以下是相同的java实现:

public int sum2(TreeNode A, int B) {
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    TreeNode cur1 = A;
    TreeNode cur2 = A;

    while (!stack1.isEmpty() || !stack2.isEmpty() ||
            cur1 != null || cur2 != null) {
        if (cur1 != null || cur2 != null) {
            if (cur1 != null) {
                stack1.push(cur1);
                cur1 = cur1.left;
            }

            if (cur2 != null) {
                stack2.push(cur2);
                cur2 = cur2.right;
            }
        } else {
            int val1 = stack1.peek().val;
            int val2 = stack2.peek().val;

            // need to break out of here
            if (stack1.peek() == stack2.peek()) break;

            if (val1 +  val2 == B) return 1;

            if (val1 + val2 < B) {
                cur1 = stack1.pop();
                cur1 = cur1.right;
            } else {
                cur2 = stack2.pop();
                cur2 = cur2.left;
            }
        }
    }

    return 0;
}
于 2015-10-30T16:55:50.877 回答
0

来自http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

/* In a balanced binary search tree isPairPresent two element which sums to
   a given value time O(n) space O(logn) */
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

// A BST node
struct node
{
    int val;
    struct node *left, *right;
};

// Stack type
struct Stack
{
    int size;
    int top;
    struct node* *array;
};

// A utility function to create a stack of given size
struct Stack* createStack(int size)
{
    struct Stack* stack =
        (struct Stack*) malloc(sizeof(struct Stack));
    stack->size = size;
    stack->top = -1;
    stack->array =
        (struct node**) malloc(stack->size * sizeof(struct node*));
    return stack;
}

// BASIC OPERATIONS OF STACK
int isFull(struct Stack* stack)
{   return stack->top - 1 == stack->size;  }

int isEmpty(struct Stack* stack)
{   return stack->top == -1;   }

void push(struct Stack* stack, struct node* node)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = node;
}

struct node* pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top--];
}

// Returns true if a pair with target sum exists in BST, otherwise false
bool isPairPresent(struct node *root, int target)
{
    // Create two stacks. s1 is used for normal inorder traversal
    // and s2 is used for reverse inorder traversal
    struct Stack* s1 = createStack(MAX_SIZE);
    struct Stack* s2 = createStack(MAX_SIZE);

    // Note the sizes of stacks is MAX_SIZE, we can find the tree size and
    // fix stack size as O(Logn) for balanced trees like AVL and Red Black
    // tree. We have used MAX_SIZE to keep the code simple

    // done1, val1 and curr1 are used for normal inorder traversal using s1
    // done2, val2 and curr2 are used for reverse inorder traversal using s2
    bool done1 = false, done2 = false;
    int val1 = 0, val2 = 0;
    struct node *curr1 = root, *curr2 = root;

    // The loop will break when we either find a pair or one of the two
    // traversals is complete
    while (1)
    {
        // Find next node in normal Inorder traversal. See following post
        // http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
        while (done1 == false)
        {
            if (curr1 != NULL)
            {
                push(s1, curr1);
                curr1 = curr1->left;
            }
            else
            {
                if (isEmpty(s1))
                    done1 = 1;
                else
                {
                    curr1 = pop(s1);
                    val1 = curr1->val;
                    curr1 = curr1->right;
                    done1 = 1;
                }
            }
        }

        // Find next node in REVERSE Inorder traversal. The only
        // difference between above and below loop is, in below loop
        // right subtree is traversed before left subtree
        while (done2 == false)
        {
            if (curr2 != NULL)
            {
                push(s2, curr2);
                curr2 = curr2->right;
            }
            else
            {
                if (isEmpty(s2))
                    done2 = 1;
                else
                {
                    curr2 = pop(s2);
                    val2 = curr2->val;
                    curr2 = curr2->left;
                    done2 = 1;
                }
            }
        }

        // If we find a pair, then print the pair and return. The first
        // condition makes sure that two same values are not added
        if ((val1 != val2) && (val1 + val2) == target)
        {
            printf("\n Pair Found: %d + %d = %d\n", val1, val2, target);
            return true;
        }

        // If sum of current values is smaller, then move to next node in
        // normal inorder traversal
        else if ((val1 + val2) < target)
            done1 = false;

        // If sum of current values is greater, then move to next node in
        // reverse inorder traversal
        else if ((val1 + val2) > target)
            done2 = false;

        // If any of the inorder traversals is over, then there is no pair
        // so return false
        if (val1 >= val2)
            return false;
    }
}

// A utility function to create BST node
struct node * NewNode(int val)
{
    struct node *tmp = (struct node *)malloc(sizeof(struct node));
    tmp->val = val;
    tmp->right = tmp->left =NULL;
    return tmp;
}

// Driver program to test above functions
int main()
{
    /*
                   15
                /     \
              10      20
             / \     /  \
            8  12   16  25    */
    struct node *root =  NewNode(15);
    root->left = NewNode(10);
    root->right = NewNode(20);
    root->left->left = NewNode(8);
    root->left->right = NewNode(12);
    root->right->left = NewNode(16);
    root->right->right = NewNode(25);

    int target = 28;
    if (isPairPresent(root, target) == false)
        printf("\n No such values are found\n");

    getchar();
    return 0;
}
于 2014-01-18T12:38:52.963 回答
0

据我所知,O(log n) 是您可以使用的最佳搜索函数。我对“n”感兴趣。如果您在某处使用 for 循环,请考虑使用哈希表来代替。如果我没记错的话,哈希表查找是 O(1)。

于 2013-09-20T01:16:53.087 回答
0

我在陈庞的回答下发现了一个错误,否则它是完美的。错误正在删除方法下。remove除了迭代器下的方法外,所有其他代码都相同

假设我们有树,根据 Chen Pang 的回答,它不会考虑元素 18。同样对于左迭代器

                     10
                          20
                       15     25
                    13    18


class BinTreeIterator implements Iterator<BinTreeNode> {
    Stack<BinTreeNode> stack;
    boolean leftToRight;

    public boolean hasNext() {
        return !stack.empty();
    }

    public BinTreeNode next() {
        return stack.peek();
    }

    public void remove() {
        BinTreeNode node = stack.pop();
        if (leftToRight) {
            node = node.rightChild;
            while (node.rightChild != null) {
                stack.push(node);

                BinTreeNode leftNode=node.leftChild;
                while (leftNode != null) {
                    stack.push(leftNode);
                    leftNode= node.leftChild;
                }

                node = node.rightChild;
            }
        } else {
            node = node.leftChild;
            while (node.leftChild != null) {
                stack.push(node);

                BinTreeNode rightNode=node.rightChild;
                while (rightNode != null) {
                    stack.push(rightNode);
                    rightNode= node.rightChild;
                }

                node = node.leftChild;
            }
        }
    }

    public BinTreeIterator(BinTreeNode node, boolean leftToRight) {
        stack = new Stack<BinTreeNode>();
        this.leftToRight = leftToRight;

        if (leftToRight) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
        } else {
            while (node != null) {
                stack.push(node);
                node = node.rightChild;
            }
        }            
    }

    public static boolean searchNumBinTree(BinTreeNode node, int num) {
        if (node == null)
            return false;

        BinTreeIterator leftIter = new BinTreeIterator(node,true);
        BinTreeIterator rightIter = new BinTreeIterator(node,false);

        while (leftIter.hasNext() && rightIter.hasNext()) {
            BinTreeNode left = leftIter.next();
            BinTreeNode right = rightIter.next();
            int sum = left.item + right.item;
            if (sum == num) {
                return true;
            } else if (sum > num) {
                rightIter.remove();
                if (!rightIter.hasNext() || rightIter.next() == left) {
                    return false;
                }
            } else {
                leftIter.remove();
                if (!leftIter.hasNext() || leftIter.next() == right) {
                    return false;
                }
            }
        }

        return false;
    }

    private static class BinTreeNode{

        BinTreeNode leftChild;
        BinTreeNode rightChild;

    }
}
于 2016-09-26T08:32:31.357 回答
0
    public boolean nodeSum(Node root, int num){
             /*
               Just subtract the sum from current value of the node and find
the node with remainder.
              */
              if(root==null){
                  return false;
              }
              int val=num-root.key;

              boolean found=find(root,val);
              if(found){
                  return true;
                  }

              boolean lSum=nodeSum(root.left,num);
              boolean rSum=nodeSum(root.right,num);
              return lSum||rSum;

          }
          public boolean find(Node root, int k){//same as search
        if(root==null){
            return false;
        }
        if(root.key==k){
            return true;
        }
        if(root.key<k){
            return find(root.right,k);
        }else{
            return find(root.left, k);
        }
    }
于 2017-01-19T18:20:01.083 回答