home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Two Sum IV - อินพุตเป็น BST ใน C++

ปัญหา

สมมติว่าเรามี Binary Search Tree และค่าเป้าหมายหนึ่งค่า เราต้องตรวจสอบว่ามีสมาชิกสองตัวใน BST ที่ผลรวมเท่ากับเป้าหมายที่กำหนดหรือไม่

เช่น ถ้าผนวกเข้าเป็น (รูปภาพ BST) ผลลัพธ์จะเป็น True

วิธีแก้ปัญหา

  1. กำหนดอาร์เรย์ v
  2. กำหนดฟังก์ชัน inorder() รับ root:
    • ถ้า root เป็น null: คืนค่า
    • inorder(left of root)
    • เพิ่มค่าของ root เข้า v
    • inorder(right of root)
  3. กำหนดฟังก์ชัน findnode() รับ k:
    • n := ขนาดของ v
    • while i < j ทำ:
      • t := v[i] + v[j]
      • ถ้า t เท่ากับ k: คืนค่า true
      • ถ้า t < k: เพิ่ม i ขึ้น 1
      • มิฉะนั้น: ลด j ลง 1
    • คืนค่า false
  4. จากเมธอดหลัก:
    • inorder(root)
    • จัดเรียงอาร์เรย์ v
    • คืนค่า findnode(k)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

class TreeNode{ 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data){ 
        val = data; 
        left = NULL; 
        right = NULL; 
    } 
}; 

void insert(TreeNode **root, int val){ 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()){ 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left){ 
            if(val != NULL) 
                temp->left = new TreeNode(val); 
            else 
                temp->left = new TreeNode(0); 
            return; 
        } else{ 
            q.push(temp->left); 
        } 
        if(!temp->right){ 
            if(val != NULL) 
                temp->right = new TreeNode(val); 
            else 
                temp->right = new TreeNode(0); 
            return; 
        } else{ 
            q.push(temp->right); 
        } 
    } 
} 

TreeNode *make_tree(vector<int> v){ 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; ival == 0) 
            return; 
        inorder(root->left); 
        v.push_back(root->val); 
        inorder(root->right); 
    } 

    bool findnode(int k){ 
        int n = v.size(), i = 0, j = n - 1; 
        while (i < j) { 
            int t = v[i] + v[j]; 
            if (t == k) 
                return true; 
            if (t < k) 
                i++; 
            else 
                j--; 
        } 
        return false; 
    } 

    bool findTarget(TreeNode* root, int k){ 
        inorder(root); 
        sort(v.begin(), v.end()); 
        return findnode(k); 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {5,3,6,2,4,NULL,7}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.findTarget(root, 9)); 
}

อินพุต

{5,3,6,2,4,NULL,7},9

เอาต์พุต

1