ຄວາມເລິກສູງສຸດຂອງການແກ້ໄຂບັນຫາ Leetcode Tree Binary


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ເຟສບຸກ Microsoft
ຕົ້ນໄມ້ຖານສອງ Recursion Traversal ຕົ້ນໄມ້

ຖະແຫຼງການບັນຫາ

ໃນບັນຫາກ ຕົ້ນໄມ້ຖານສອງ ແມ່ນໃຫ້ແລະພວກເຮົາຕ້ອງຊອກຫາຄວາມເລິກສູງສຸດຂອງຕົ້ນໄມ້ທີ່ໃຫ້. ຄວາມເລິກສູງສຸດຂອງຕົ້ນໄມ້ໄບນາລີແມ່ນ ຈຳ ນວນຂອງຂໍ້ທີ່ຢູ່ຕາມເສັ້ນທາງທີ່ຍາວທີ່ສຸດຈາກຂໍ້ຮາກລົງຫາຂໍ້ໃບໄມ້ທີ່ໄກທີ່ສຸດ.

ຍົກຕົວຢ່າງ

 
  3
 / \
9   20
   /  \		 
  15   7
3

ຄຳ ອະທິບາຍ: ມີສອງເສັ້ນທາງທີ່ຍາວທີ່ສຸດເທົ່າທີ່ເປັນໄປໄດ້ດັ່ງທີ່ສະແດງຢູ່ໃນຕົ້ນໄມ້ສີແດງ.
ຄວາມເລິກສູງສຸດຂອງການແກ້ໄຂບັນຫາ Leetcode Tree Binary

Empty Tree
0

ໃນຖານະເປັນຕົ້ນໄມ້ແມ່ນຫວ່າງເປົ່າ, ຄວາມເລິກແມ່ນ 0.

0
1

ຍ້ອນວ່າມີພຽງຂໍ້ ໜຶ່ງ ເທົ່ານັ້ນ, ຄວາມເລິກແມ່ນ 1.

ວິທີການ

ເພື່ອຊອກຫາຄວາມເລິກສູງສຸດຂອງຕົ້ນໄມ້ພວກເຮົາສາມາດ ນຳ ໃຊ້ວິທີການລວບລວມແບບງ່າຍໆ. ບ່ອນທີ່ແຕ່ລະ ໜ້າ ທີ່ເອີ້ນການເຮັດວຽກຈະເປັນຕົວແທນຂອງລັດຖະບັນຍັດເຊິ່ງມີ node ຮາກເອີ້ນວ່າ 'ຮາກ'. ພວກເຮົາຂ້າມຕົ້ນໄມ້ໂດຍການເຮັດ ໜ້າ ທີ່ເອີ້ນຫາເລີ່ມຈາກຮາກຂໍ້.

ດັ່ງນັ້ນກໍລະນີພື້ນຖານແມ່ນເວລາທີ່ລັດຖະບັນຍັດແມ່ນຫວ່າງເປົ່າ. ຮາກແມ່ນ NULL. ດັ່ງນັ້ນພວກເຮົາກັບຄືນຄວາມເລິກເປັນ 0.

ຖ້າຮາກບໍ່ແມ່ນ NULL, ໃຫ້ໂທຫາຟັງຊັນດຽວກັນກັບເດັກນ້ອຍຊ້າຍແລະຂວາຂອງມັນ.

ດັ່ງທີ່ສະແດງຢູ່ໃນຮູບ, ໃນເວລາທີ່ ໜ້າ ທີ່ຂອງເດັກສອງຄົນກັບຄືນຄວາມເລິກຂອງມັນພວກເຮົາເລືອກເອົາສູງສຸດອອກຈາກທັງສອງບົດບັນຍັດນີ້ແລະສົ່ງຄືນຄ່ານີ້ຫຼັງຈາກເພີ່ມ 1 ໃສ່ມັນ (ເພີ່ມ node ປະຈຸບັນເຊິ່ງແມ່ນພໍ່ແມ່ຂອງທັງສອງລັດຖະມົນຕີ).

ຄວາມເລິກສູງສຸດຂອງຕົ້ນໄມ້ຖານສອງ

ການປະຕິບັດ

ໂຄງການ C ++ ສຳ ລັບຄວາມເລິກສູງສຸດຂອງການແກ້ໄຂບັນຫາ Leetcode Tree Binary

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int maxDepth(TreeNode* root) 
{
    if(root==NULL) return 0;
    return 1+max(maxDepth(root->left),maxDepth(root->right));
}

int main() 
{
    TreeNode *root= new TreeNode(3);
    root->left= new TreeNode(9);
    root->right= new TreeNode(20);
    root->right->left= new TreeNode(15);
    root->right->right= new TreeNode(7);
    
    cout<<maxDepth(root)<<endl; 
  return 0; 
}
3

Java Program ສຳ ລັບຄວາມເລິກສູງສຸດຂອງ Binary Tree Leetcode Solution

import java.util.*;
import java.lang.*;
class TreeNode 
{
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) 
      {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class MaxDepth
{  
    public static int maxDepth(TreeNode root) 
    {
        if(root==null) return 0;
        
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    
    public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left= new TreeNode(9);
        root.right= new TreeNode(20);
        root.right.left= new TreeNode(15);
        root.right.right= new TreeNode(7);
       
        System.out.println(maxDepth(root));
        
    }
}
3

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບຄວາມເລິກສູງສຸດຂອງການແກ້ໄຂບັນຫາ Leetcode Tree Binary

ຄວາມສັບສົນເວລາ

O (N):  ພວກເຮົາໄປຢ້ຽມຢາມແຕ່ລະ node ຢ່າງແນ່ນອນຄັ້ງ ໜຶ່ງ, ດັ່ງນັ້ນຄວາມສັບສົນເວລາແມ່ນ O (N), ບ່ອນທີ່ N ແມ່ນ ຈຳ ນວນທັງ ໝົດ ຂອງຂໍ້ໃນຕົ້ນໄມ້ທີ່ໃຫ້.

ຄວາມສັບສົນໃນອະວະກາດ 

O (N):  ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ, ຕົ້ນໄມ້ແມ່ນບໍ່ສົມດຸນສົມບູນ, ຕົວຢ່າງແຕ່ລະຂໍ້ໄດ້ປ່ອຍໃຫ້ເດັກນ້ອຍອອກຈາກຫຼືມີພຽງແຕ່ຂໍ້ເດັກນ້ອຍທີ່ຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນການໂທຫາການຮຽກຄືນຈະເກີດຂື້ນ N ເທື່ອ (ລະດັບຄວາມສູງຂອງຕົ້ນໄມ້). ສະນັ້ນຂະ ໜາດ ສູງສຸດຂອງການໂທຫາສຽງຈະເປັນ O (N).
ໃນກໍລະນີທີ່ດີທີ່ສຸດ (ຕົ້ນໄມ້ແມ່ນສົມດຸນສົມບູນ), ລະດັບຄວາມສູງຂອງຕົ້ນໄມ້ຈະເປັນໄມ້ທ່ອນ (N). ສະນັ້ນ, ຄວາມສັບສົນໃນອະວະກາດໃນກໍລະນີນີ້ແມ່ນ O (log⁡ (N)).