Minimum Depth of Binary Tree ใน C++

แนวคิด

สมมติว่ามี binary tree ให้หาความลึกขั้นต่ำของต้นไม้นี้ ความลึกขั้นต่ำคือจำนวนโหนดตามเส้นทางสั้นที่สุดจากโหนดรากลงสู่โหนดใบที่ใกล้ที่สุด

เช่น ถ้าอินพุตเป็น:

ผลลัพธ์คือ 2

วิธีแก้:

• กำหนดอาร์เรย์ aa ของ tree nodes
• แทรก root ลงท้าย aa
• กำหนดอีกอาร์เรย์ ak ของ tree nodes
• level := 0
• ถ้า root เป็น null: คืนค่า 0
• while ขนาด aa ไม่เท่ากับ 0:
  • ล้างอาร์เรย์ ak
  • เพิ่ม level ขึ้น 1
  • สำหรับทุกโหนด a ใน aa:
    • ถ้า (left of a เป็น null) และ (right of a เป็น null): คืนค่า level, ออกจากลูป
    • ถ้า left of a ไม่ใช่ null: แทรก left of a ลงท้าย ak
    • ถ้า right of a ไม่ใช่ null: แทรก right of a ลงท้าย ak
  • aa := ak
• คืนค่า 0

ตัวอย่าง

#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; i<v.size(); i++){ insert(&root, v[i]); }
    return root;
}
class Solution {
public:
    int minDepth(TreeNode* root) {
        vector<TreeNode*> aa;
        aa.push_back(root);
        vector<TreeNode*> ak;
        int level = 0;
        if (root == NULL || root->val == 0) { return 0; }
        while (aa.size() != 0) {
            ak.clear();
            level++;
            for (TreeNode* a : aa) {
                if ((a->left == NULL || a->left->val == 0) && (a->right == NULL || a->right->val == 0)) {
                    return level;
                    break;
                }
                if (a->left != NULL) { ak.push_back(a->left); }
                if (a->right != NULL) { ak.push_back(a->right); }
            }
            aa = ak;
        }
        return 0;
    }
};
main() {
    Solution ob;
    vector<int> v = {3,9,20,NULL,NULL,15,7};
    TreeNode *root = make_tree(v);
    cout << (ob.minDepth(root));
}

อินพุต

{3,9,20,NULL,NULL,15,7}

เอาต์พุต

2