1. <dd id="erndk"></dd>
                1. 【697】力扣中的二叉樹 based on python

                  互聯網 2022/5/2 12:42:43

                  二叉樹算是比較難得數據結構,相對于常見的數據結構而言更加抽象,本文主要是針對力扣中相關二叉樹的問題進行說明,也是因為自己在做題中來逐漸學習和復習的過程!首先幾點說明如下:判斷是否存在根節點,可以直接 if root: ,也可以通過賦值來判斷 if root == None: 以及…

                    二叉樹算是比較難得數據結構,相對于常見的數據結構而言更加抽象,本文主要是針對力扣中相關二叉樹的問題進行說明,也是因為自己在做題中來逐漸學習和復習的過程!

                    首先幾點說明如下:

                  • 判斷是否存在根節點,可以直接 if root: ,也可以通過賦值來判斷 if root == None: 以及 if root is None: 。

                  • 對于題目中給出的輸入數據以數組形式顯示,這個不用理會具體是通過怎樣的遍歷方式顯示的,跟具體的解題沒有關系,只是顯示而已,具體的解題還是完全根據二叉樹本身的結構和性質來實現!

                  • 針對二叉樹的操作,需要多次運用到遞歸的思想,一個問題可能用到兩次遞歸都是有可能的。

                  • 另外,可以通過 print 來調試程序,選擇“執行代碼”的時候也會打印出對應的信息,因為針對二叉樹的問題,不容易在本地IDE上面處理,因為需要創建二叉樹,不像數組那么簡單!

                  1. #94 二叉樹的中序遍歷

                    二叉樹的主要遍歷就是

                  • 先序遍歷

                  • 中序遍歷

                  • 后序遍歷

                  • 層次遍歷

                    主要思想就是遞歸,設置一個出口!

                  # Definition for a binary tree node.
                  # class TreeNode:
                  #     def __init__(self, val=0, left=None, right=None):
                  #         self.val = val
                  #         self.left = left
                  #         self.right = right
                  class Solution:
                      def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                          if root is None:
                              return []
                          list_left = Solution.inorderTraversal(self, root.left)
                          list_middle = [root.val] 
                          list_right = Solution.inorderTraversal(self, root.right)
                  
                          return list_left + list_middle + list_right
                  

                   

                  2. #100. 相同的樹

                    直接判斷它們的遍歷結果是否一致,為了區分不同方向的樹,需要添加葉子節點的左右子樹的信息。

                  # Definition for a binary tree node.
                  # class TreeNode:
                  #     def __init__(self, val=0, left=None, right=None):
                  #         self.val = val
                  #         self.left = left
                  #         self.right = right
                  class Solution:
                      def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
                          p_list = Solution.preOrderTraverse(self, p)
                          q_list = Solution.preOrderTraverse(self, q)
                  
                          if p_list == q_list:
                              return True
                          else:
                              return False
                  
                      def preOrderTraverse(self, tn: TreeNode) -> list:
                          if tn is None:
                              return [0]  # 用來記錄空樹的信息
                  
                          middle_list = [tn.val]
                          left_list = Solution.preOrderTraverse(self, tn.left) 
                          right_list = Solution.preOrderTraverse(self, tn.right)
                  
                          return middle_list + left_list + right_list
                  

                   

                  3. #101. 對稱二叉樹

                    考慮 先序遍歷 與 后序遍歷 正好相反來構建算法

                  # Definition for a binary tree node.
                  # class TreeNode:
                  #     def __init__(self, val=0, left=None, right=None):
                  #         self.val = val
                  #         self.left = left
                  #         self.right = right
                  class Solution:
                      def isSymmetric(self, root: Optional[TreeNode]) -> bool:
                          if root and root.left == None and root.right == None: 
                              return True 
                          
                          if root.left and root.right == None or root.left == None and root.right: 
                              return False 
                          
                          pre_list = Solution.preOrderTraverse(self, root)
                          post_list = Solution.postOrderTraverse(self, root)
                  
                          if pre_list == post_list[::-1]:
                              return True
                          else:
                              return False
                  
                      def preOrderTraverse(self, root: TreeNode):
                          if root is None:
                              return [0]
                  
                          left_list = Solution.preOrderTraverse(self, root.left)
                          middle_list = [root.val] 
                          right_list = Solution.preOrderTraverse(self, root.right)
                  
                          return middle_list + left_list + right_list
                  
                      def postOrderTraverse(self, root: TreeNode):
                          if root is None:
                              return [0]
                  
                          left_list = Solution.postOrderTraverse(self, root.left)
                          middle_list = [root.val] 
                          right_list = Solution.postOrderTraverse(self, root.right)
                  
                          return left_list + right_list + middle_list
                  
                      def midOrderTraverse(self, root: TreeNode):
                          if root is None:
                              return [0]
                  
                          left_list = Solution.midOrderTraverse(self, root.left)
                          middle_list = [root.val] 
                          right_list = Solution.midOrderTraverse(self, root.right)
                  
                          return left_list + middle_list + right_list
                  

                   

                  4. #104. 二叉樹的最大深度

                    直接遞歸就行了!

                  # Definition for a binary tree node.
                  # class TreeNode:
                  #     def __init__(self, val=0, left=None, right=None):
                  #         self.val = val
                  #         self.left = left
                  #         self.right = right
                  class Solution:
                      def maxDepth(self, root: Optional[TreeNode]) -> int:
                          if root is None:
                              return 0
                          return max(Solution.maxDepth(self, root.left), Solution.maxDepth(self, root.right)) + 1
                  

                   

                  5. #

                   

                  隨時隨地學軟件編程-關注百度小程序和微信小程序
                  關于找一找教程網

                  本站文章僅代表作者觀點,不代表本站立場,所有文章非營利性免費分享。
                  本站提供了軟件編程、網站開發技術、服務器運維、人工智能等等IT技術文章,希望廣大程序員努力學習,讓我們用科技改變世界。
                  [【697】力扣中的二叉樹 based on python]http://www.yachtsalesaustralia.com/tech/detail-318731.html

                  贊(0)
                  關注微信小程序
                  程序員編程王-隨時隨地學編程

                  掃描二維碼或查找【程序員編程王】

                  可以隨時隨地學編程啦!

                  技術文章導航 更多>
                  国产在线拍揄自揄视频菠萝

                        1. <dd id="erndk"></dd>