leetcode二叉樹

二叉樹的中序周遊
驗證二叉搜尋樹
恢複二叉搜尋樹
相同的樹
對稱二叉樹
二叉樹的層序周遊
二叉樹的鋸齒形層序周遊
二叉樹的最大深度
從前序與中序周遊序列構造二叉樹
從中序與後序周遊序列構造二叉樹
路徑總和
路徑總和 II
二叉樹中的最大路徑和
二叉樹的下一個節點
樹的子結構
二叉樹的鏡像
從上到下列印二叉樹
平衡二叉樹
求根節點到葉節點數字之和
打家劫舍 III

樹的屬性：

層次結構
一個節點的所有子節點獨立于另一個節點的子節點。

二叉樹：如果樹中的每個節點最多有兩個子節點，我們說該樹是一個二叉樹。

1.清單表示的樹

在清單樹的清單中，将根節點的值存儲為清單的第一個元素；第二個元素：一個表示左子樹的清單；第三個元素：表示右子樹的另一個清單。

2.節點表示

用

left

和

right

的屬性表示其他執行個體的引用。

3 . 樹的周遊

前序 ：首先通路根節點，然後遞歸地做左子樹的前序周遊，随後是右子樹的遞歸前序周遊。
中序 ：遞歸地對左子樹進行一次周遊，通路根節點，最後遞歸周遊右子樹。
後序 ：遞歸地對左子樹、右子樹進行後序周遊，最後通路根節點。

基于二叉堆的優先隊列

在優先級隊列中，隊列中的項的邏輯順序由他們的優先級确定。最高優先級項在隊列的前面，最低優先級的項在後面。實作優先級隊列的經典方法是使用二叉堆的資料結構。二叉堆允許我們在O(logn) 中排隊和取出隊列。

堆看起來就像一棵樹，但當我們實作它時，我們隻使用一個單一的清單作為内部表示。二叉堆有兩個常見的變體：最小堆（最小的鍵在前面）和最大堆。

二叉堆的實作

完整二叉樹(平衡二叉樹)：每一層都有其所有的節點，除了樹的最底層，從左到右填充。

父節點的左子節點：2p；右子節點的位置：2p+1

二叉查找樹

二叉查找樹依賴于在左子樹中找到的鍵小于父節點的屬性，并且在右子樹中找到的鍵大于父代。

leetcode 例題練習

94. 二叉樹的中序周遊

給定一個二叉樹，傳回它的中序周遊。

示例：

輸入: [1,null,2,3]
   1
    \
     2
    /
   3

輸出: [1,3,2]

思路：中序周遊 left–>root–>right, 用遞歸算法

# 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: TreeNode) -> List[int]:
        if root ==None:
            return []
        
        # 中序周遊
        res=[]
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
         return res
        # 前序周遊
        return [root.val] +self.preorderTraversal(root.left) + self.preordertraversal(root.right)
        # 後序周遊
        return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val]
        
### 疊代法：
class Solution:
    def inorderTraversal(self,root):
        res=[]
        stack=[]
        cur=root
        ## 中序：先用指針找到子樹的最左下角
        while stack or cur:
            while cur:          # 節點為空，說明沒有左子節點
                stack.append(cur)
                cur=cur.left
            cur=stack.pop()
            res.append(cur.val)
            cur=cur.right
        return res

    ###前序疊代
    def preorderTraversal(self,root):
        stack=[root]
        res=[]
        while stack:
            node=stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res
    
    ### 後序周遊
    def postorderTraversal(root):
        res=[]
        stack=[]
        node=root
        while stack or node:
            while node:
                stack.append(node)
                if node.left:
                    node=node.left
                else:
                    node=node.right
            node=stack.pop()
            res.append(node.val)
            if stack and stack[-1].left ==node:           # 棧中不為空，且存在父節點
                node=stack[-1].right                      # 加入兄弟右節點
            else:
                node=None
        return res

98. 驗證二叉搜尋樹

給定一個二叉樹，判斷其是否是一個有效的二叉搜尋樹。

假設一個二叉搜尋樹具有如下特征：

節點的左子樹隻包含小于目前節點的數。
節點的右子樹隻包含大于目前節點的數。
所有左子樹和右子樹自身必須也是二叉搜尋樹。

示例

輸入:
    2
   / \
  1   3
輸出: true

輸入:
    5
   / \
  1   4
     / \
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
     根節點的值為 5 ，但是其右子節點值為 4 。

解題思路：利用中序周遊，根據周遊之後的數組是否有序傳回True或False

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        res=self.inorderTraversal(root)
        for i in range(len(res)-1):
            if res[i]>=res[i+1]:
                return False
        return True
    def inorderTraversal(self,root):
        if root ==None:
            return []
        res=[]
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
        return res

另一種解法：中序+棧

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        pre = None
        stack = list()
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                if pre and root.val <= pre.val:
                        return False
                
                pre = root
                root = root.right

        return True

99. 恢複二叉搜尋樹

二叉搜尋樹中的兩個節點被錯誤地交換。

請在不改變其結構的情況下，恢複這棵樹。

示例 1:

輸入: [1,3,null,null,2]

   1
  /
 3
  \
   2

輸出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

輸入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

輸出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

進階:

使用 O(n) 空間複雜度的解法很容易實作。
你能想出一個隻使用常數空間的解決方案嗎？

解題思路：檢測中序數列，交換不符合要求的節點

代碼如下：

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        self.pre=None
        self.p1,self.p2=None,None
        self.inorderTraversal(root)
        self.p2.val,self.p1.val=self.p1.val,self.p2.val
    def inorderTraversal(self,root):
        if root:
            self.inorderTraversal(root.left)          # 該步會一直遞歸到樹的最後左子樹的葉節點
            if self.pre and self.pre.val>root.val:
                if self.p1==None:
                    self.p1=self.pre
                self.p2=root
            self.pre=root       #将最低左子樹指派
            self.inorderTraversal(root.right)   # 最低樹的右子樹

100. 相同的樹

給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

示例 1:

輸入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

輸出: true

示例 2:

輸入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

輸出: false

示例 3:

輸入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

輸出: false

代碼如下：

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p == None and q ==None:
            return True
        if p == None or q == None:#[1,2][1,null,2]
            return False
        if p.val == q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        else :
            return False

101. 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

說明:

如果你可以運用遞歸和疊代兩種方法解決這個問題，會很加分

解題思路：

root為空，則直接傳回True。否則遞歸疊代:

先判斷基本情況：

左、右子樹均為空
任意一個不為空
左、右子樹值不同

如果left.val == right.val ，遞歸下去，判斷(left.left ,right.right) 和（left.right,right.left)是否同樣成立。

代碼如下：

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.helper(root.left,root.right)
    def helper(self,left,right):
        if left == None and right == None:
            return True
        elif left==None or right ==None:
            return False
        elif left.val !=right.val:
            return False
        else:
            return self.helper(left.left,right.right) and self.helper(left.right,right.left)

### 方法二： 疊代
# 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: TreeNode) -> bool:
        if not root:
            return True
        import collections
        queue=collections.deque()
        queue.append((root.left,root.right))
        while queue:
            left,right=queue.popleft()
            if not left and not right:
                continue
            if not left or not right:
                return False
            if left.val != right.val:
                return False
            queue.append((left.left,right.right))
            queue.append((left.right,right.left))
        return True

102. 二叉樹的層序周遊

給你一個二叉樹，請你傳回其按層序周遊得到的節點值。（即逐層地，從左到右通路所有節點）。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        from collections import deque    # 廣度優先周遊： 隊列結構
        if not root:
            return []
        queue=deque()
        queue.append(root)
        res=[]
        while queue:
            cur_level=[]           # 存放目前節點的值
            for _ in range(len(queue)):
                node=queue.popleft()
                cur_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(cur_level)
        return res

103. 二叉樹的鋸齒形層序周遊

給定一個二叉樹，傳回其節點值的鋸齒形層序周遊。（即先從左往右，再從右往左進行下一層周遊，以此類推，層與層之間交替進行）。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack=[root]
        res=[]
        is_even_layer=True
        import collections
        while stack:
            cur_level=collections.deque()           # 雙端隊列存放目前層的節點值
            nodes=[]                                # 臨時棧：存放下一輪的值
            for  q in stack:            # 每輪都把目前層的節點周遊完，并把下一層的節點存放在臨時棧中，并重新指派給循環棧
                if is_even_layer:
                    cur_level.append(q.val)
                else:
                    cur_level.appendleft(q.val)
                if q.left:
                    nodes.append(q.left)
                if q.right:
                    nodes.append(q.right)
            stack=nodes
            is_even_layer= not is_even_layer
            res.append(list(cur_level))
        return res

104. 二叉樹的最大深度

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例：

給定二叉樹 [3,9,20,null,null,15,7]，

傳回它的最大深度 3 。

方法1 ：遞歸思想

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

方法2 疊代思想

# 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: TreeNode) -> int:
        if not root :
            return 0
        from collections  import deque
        queue=deque()
        queue.append((root,1))           # 存放目前的節點值以及根節點到目前節點的深度
        res=0                  
        while queue:
            node,depth=queue.popleft()       # 先進入節點的值
            if node :
                res=max(res,depth)
                queue.extend([(node.left,depth+1),(node.right,depth+1)])
        return res

105. 從前序與中序周遊序列構造二叉樹

前序周遊

preorder = [3,9,20,15,7]

中序周遊

inorder = [9,3,15,20,7]

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return 
        root =TreeNode(preorder[0])
        idx=inorder.index(preorder[0])
        root.left=self.buildTree(preorder[1:idx+1],inorder[:idx])
        root.right=self.buildTree(preorder[1+idx:],inorder[idx+1:])
        return root

112. 路徑總和

給你二叉樹的根節點 root 和一個表示目标和的整數 targetSum ，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目标和 targetSum 。

# 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 hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if not root:
            return False
        stack=[]
        stack.append((root,root.val))
        while stack:
            node,path=stack.pop(0)
            if not node.left and not node.right and path ==targetSum:
                return True
            if node.left:
                stack.append((node.left,path+node.left.val))
            if node.right:
                stack.append((node.right,path+node.right.val))
        return False

113. 路徑總和 II

給定一個二叉樹和一個目标和，找到所有從根節點到葉子節點路徑總和等于給定目标和的路徑。

# 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 pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        res=[]
        self.dfs(root,targetSum,res,[])
        return res
    
    def dfs(self,root,targetSum,res,path):
        if not root:        # 空節點，不做處理
            return 
        if not root.left and not root.right and  root.val==targetSum:
            res.append(path+[root.val])
        self.dfs(root.left,targetSum-root.val,res,path+[root.val])    
        self.dfs(root.right,targetSum-root.val,res,path+[root.val])   # 程式執行完這部分的代碼，就表示dfs函數執行完成

124. 二叉樹中的最大路徑和

路徑被定義為一條從樹中任意節點出發，沿父節點-子節點連接配接，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點

leetcode二叉樹

# 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 __init__(self):
        self.maxSum = float("-inf")
    def maxPathSum(self, root: TreeNode) -> int:
        def maxGain(node):
            if not node :      # 遞歸邊界
                return 0
            # 遞歸計算左右節點的最大貢獻值
            leftGain=max(maxGain(node.left),0)    # 遞歸調用
            rightGain=max(maxGain(node.right),0)

            # 節點的最大路徑和取決于該節點的值與該節點左右子節點的最大貢獻值
            priceNewpath = node.val + leftGain + rightGain
            self.maxSum = max(self.maxSum, priceNewpath) # 從下往上更新最值

            # 傳回目前節點的操作值
            return  node.val + max(leftGain, rightGain) # 傳回目前節點的最大貢獻值
        maxGain(root)
        return self.maxSum

二叉樹的下一個節點

給定一個二叉樹和其中的一個結點，請找出中序周遊順序的下一個結點并且傳回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。

class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    def getNext(self, node):
        # 1. 尋找右子樹，如果存在就一直找到右子樹的最左邊，就是下一個節點
        if node.right:
            tmp = node.right
            while tmp.left:
                tmp = tmp.left
            return tmp
        # 2. 沒有右子樹，就尋找它的父節點，一直找到它是父節點的左子樹，列印父節點
        else:
            while node.next:
                if node.next.left != node:
                    node = node.next
                else:
                    return node.next
            return None

劍指 Offer 26. 樹的子結構

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        result=False
        if A and B:
            if A.val==B.val:
                result=self.isequal(A,B)
            if  not result:
                result=self.isSubStructure(A.left,B)
            if not result:
                result=self.isSubStructure(A.right,B)
        return result
    
    def isequal(self,root1,root2):
        if not root2:
            return True
        if not root1:
            return False
        if root1.val !=root2.val:
            return False
        return self.isequal(root1.left,root2.left) and self.isequal(root1.right,root2.right)

劍指 Offer 27. 二叉樹的鏡像

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            node.left, node.right = node.right, node.left
        return root

劍指 Offer 32 - I. 從上到下列印二叉樹

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        result=[]
        stack=[]
        if root ==None:
            return result
        stack.append(root)
        while stack:
            node=stack.pop(0)
            result.append(node.val)
            if node.left!=None:
                stack.append(node.left)
            if node.right!=None:
                stack.append(node.right)
        return result

129. 求根節點到葉節點數字之和

leetcode二叉樹

輸入：root = [1,2,3]
輸出：25
解釋：
從根到葉子節點路徑 1->2 代表數字 12
從根到葉子節點路徑 1->3 代表數字 13
是以，數字總和 = 12 + 13 = 25

方法一：深度優先搜尋

思路與算法：

深度優先搜尋是很直覺的做法。從根節點開始，周遊每個節點，如果遇到葉子節點，則将葉子節點對應的數字加到數字之和。如果目前節點不是葉子節點，則計算其子節點對應的數字，然後對子節點遞歸周遊。

leetcode二叉樹

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, prevTotal: int) -> int:
            if not root:
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)

        return dfs(root, 0)

方法二：廣度優先搜尋

思路與算法：

使用廣度優先搜尋，需要維護兩個隊列，分别存儲節點和節點對應的數字。

初始時，将根節點和根節點的值分别加入兩個隊列。每次從兩個隊列分别取出一個節點和一個數字，進行如下操作：

如果目前節點是葉子節點，則将該節點對應的數字加到數字之和；
如果目前節點不是葉子節點，則獲得目前節點的非空子節點，并根據目前節點對應的數字和子節點的值計算子節點對應的數字，然後将子節點和子節點對應的數字分别加入兩個隊列。

搜尋結束後，即可得到所有葉子節點對應的數字之和。

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0

        total = 0
        nodeQueue = collections.deque([root])
        numQueue = collections.deque([root.val])
        
        while nodeQueue:
            node = nodeQueue.popleft()
            num = numQueue.popleft()
            left, right = node.left, node.right
            if not left and not right:
                total += num
            else:
                if left:
                    nodeQueue.append(left)
                    numQueue.append(num * 10 + left.val)
                if right:
                    nodeQueue.append(right)
                    numQueue.append(num * 10 + right.val)

        return total

337. 打家劫舍 III

class Solution:
    def rob(self, root: TreeNode) -> int:
        def DFS(root):
            if not root:
                return 0, 0
            # 後序周遊
            leftchild_steal, leftchild_nosteal = DFS(root.left)
            rightchild_steal, rightchild_nosteal = DFS(root.right)

            # 偷目前node，則最大收益為【偷目前節點+不偷左右子樹】
            steal = root.val + leftchild_nosteal + rightchild_nosteal
            # 不偷目前node，則可以偷左右子樹
            nosteal = max(leftchild_steal, leftchild_nosteal) + max(rightchild_steal, rightchild_nosteal)
            return steal, nosteal
            
        return max(DFS(root))

leetcode二叉樹

目錄

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希