337. 打家劫舍 III

144. 二叉樹的前序周遊

94. 二叉樹的中序周遊

145. 二叉樹的後序周遊

589. N叉樹的前序周遊

590. N叉樹的後序周遊

102. 二叉樹的層序周遊

559. N叉樹的最大深度

1022. 從根到葉的二進制數之和

538. 把二叉搜尋樹轉換為累加樹

337. 打家劫舍 III

https://leetcode-cn.com/problems/house-robber-iii/

在上次打劫完一條街道之後和一圈房屋後，小偷又發現了一個新的可行竊的地區。這個地區隻有一個入口，我們稱之為“根”。除了“根”之外，每棟房子有且隻有一個“父“房子與之相連。一番偵察之後，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。如果兩個直接相連的房子在同一天晚上被打劫，房屋将自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

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

leetcode-樹（三）337. 打家劫舍 III144. 二叉樹的前序周遊94. 二叉樹的中序周遊145. 二叉樹的後序周遊589. N叉樹的前序周遊590. N叉樹的後序周遊102. 二叉樹的層序周遊559. N叉樹的最大深度1022. 從根到葉的二進制數之和538. 把二叉搜尋樹轉換為累加樹

輸出: 7 解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.

示例 2:輸入: [3,4,5,1,3,null,1]

輸出: 9 解釋: 小偷一晚能夠盜取的最高金額 = 4 + 5 = 9.

題解

一：DFS+記憶化。

class Solution(object):
    def __init__(self):
        self.rec = {}
    # 以root為根的最大值
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if root in self.rec:
            return self.rec[root]
        cur_val = root.val
        if root.left:
            cur_val += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            cur_val += self.rob(root.right.left) + self.rob(root.right.right)
        self.rec[root] = max(cur_val, self.rob(root.left) + self.rob(root.right))
        return self.rec[root]

二：轉https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/大神解法。

leetcode-樹（三）337. 打家劫舍 III144. 二叉樹的前序周遊94. 二叉樹的中序周遊145. 二叉樹的後序周遊589. N叉樹的前序周遊590. N叉樹的後序周遊102. 二叉樹的層序周遊559. N叉樹的最大深度1022. 從根到葉的二進制數之和538. 把二叉搜尋樹轉換為累加樹

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        res = self.DFS(root)
        return max(res[0], res[1])
        
    # 傳回：第一個表示不偷root的最大值，第二個表示偷root的最大值
    def DFS(self, root):
        if not root:
            return [0, 0]
        left_val = self.DFS(root.left)
        right_val = self.DFS(root.right)
        res = [0, 0]
        res[0] = max(left_val) + max(right_val)
        res[1] = left_val[0] + right_val[0] + root.val
        return res

144. 二叉樹的前序周遊

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

題解

一：遞歸，二叉樹周遊，左子樹一定在右子樹之前，前中後說的是根節點的通路順序。前序周遊：根->左->右。

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res 
        res.append(root.val)
        res.extend(self.preorderTraversal(root.left))
        res.extend(self.preorderTraversal(root.right))
        return res

二：疊代，借助棧的結構，先進後出。每次往q的末尾加入元素，也從末尾彈出元素。visit指令表示經過該節點并壓棧，add指令表示周遊該節點即将其加入res清單中。else結構中的順序與周遊順序（根->左->右）剛好相反。

class Solution(object):
    def preorderTraversal(self, root):
        stack, ans = [], []
        if not root:
            return ans
        stack.append((root, "visited"))
        while stack:
            node, command = stack.pop()
            if command == 'add':
                ans.append(node.val)
            else:
                if node.right:
                    stack.append((node.right, "visited"))
                if node.left:
                    stack.append((node.left, "visited"))
                stack.append((node, 'add'))
        return ans

class Solution(object):
    def preorderTraversal(self, root):
        stack, ans = [], []
        if not root:
            return ans
        stack.append(root)
        while stack:
            node = stack.pop()
            ans += [node.val]
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            
        return ans

94. 二叉樹的中序周遊

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

題解

一：遞歸，中序周遊：左->根->右。

class Solution(object):
    def inorderTraversal(self, root):
        ans = []
        if not root:
            return ans 
        if root.left:
            ans += self.inorderTraversal(root.left)
        ans += [root.val]
        if root.right:
            ans += self.inorderTraversal(root.right)
        return ans

二：疊代，else結構中的順序與周遊順序（左->根->右）剛好相反。

class Solution(object):
    def inorderTraversal(self, root):
        ans, stack = [], []
        if not root:
            return ans
        stack.append((root, 'visited'))
        while stack:
            node, command = stack.pop()
            if command == 'add':
                ans.append(node.val)
            else:
                if node.right:
                    stack.append((node.right, 'visited'))
                stack.append((node, 'add'))
                if node.left:
                    stack.append((node.left, 'visited'))

        return ans

145. 二叉樹的後序周遊

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

題解

一：遞歸，後序周遊：左->右->根。

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res 
        res.extend(self.postorderTraversal(root.left))
        res.extend(self.postorderTraversal(root.right))
        res.append(root.val)   
        return res

二：：疊代，else結構中的順序與周遊順序（左->右->根）剛好相反。

from collections import deque
class Solution(object):
    def postorderTraversal(self, root):
        res, q = [], deque()
        if not root:
            return res 
        q.append((root, "visit"))

        while q:
            node, command = q.pop()
            if command == "add":
                res.append(node.val)
            else:
                q.append((node, "add"))
                if node.right:
                    q.append((node.right, "visit"))
                if node.left:
                    q.append((node.left, "visit"))
                  
        return res

589. N叉樹的前序周遊

https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

題解

一：遞歸，self.children中的children是一個清單，清單中的元素是該節點的子節點

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        res = []
        if not root:
            return res 
        res.append(root.val)
        for children in root.children:
            res += self.preorder(children)
        return res

二：疊代，注意node.children[::-1]

from collections import deque
class Solution(object):
    def preorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        res = []
        if not root:
            return res 
        q = deque() 
        q.append((root, "visit"))

        while q:
            node, command = q.pop()
            if command == "add":
                res.append(node.val)
            else:
                for child in node.children[::-1]:
                    q.append((child, "visit"))
                q.append((node, "add"))
        return res

590. N叉樹的後序周遊

https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/

題解

一：遞歸

class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        for child in root.children:
            res += self.postorder(child)
        res += [root.val]
        return res

二：疊代

from collections import deque
class Solution(object):
    def postorder(self, root):
        res = []
        if not root:
            return res
        q = deque()
        q.append((root, "visit"))

        while q:
            node, command = q.pop()
            if command == "add":
                res.append(node.val)
            else:
                q.append((node, "add"))
                for child in node.children[::-1]:
                    q.append((child, "visit"))        
        return res

102. 二叉樹的層序周遊

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

題解

一：借用隊列結構，先進先出。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        
        q, res = deque(), []
        q.append(root)

        while q:
            n = len(q) 
            res.append([])
            for i in range(n):
                node = q.popleft()
                res[-1].append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return res

559. N叉樹的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

題解

一：遞歸，DFS

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        res = 0
        if not root:
            return res 
        for child in root.children:
            res = max(res, self.maxDepth(child))
        res += 1
        return res

二：疊代，BFS，層序周遊

from collections import deque
class Solution(object):
    def maxDepth(self, root):
        if not root:
            return 0 
        res, q = 0, deque()
        q.append(root)

        while q:
            n = len(q)
            for i in range(n):
                node = q.popleft()
                for child in node.children:
                    q.append(child)
            res += 1

        return res

1022. 從根到葉的二進制數之和

https://leetcode-cn.com/problems/sum-of-root-to-leaf-binary-numbers/

給出一棵二叉樹，其上每個結點的值都是 0 或 1 。每一條從根到葉的路徑都代表一個從最高有效位開始的二進制數。例如，如果路徑為 0 -> 1 -> 1 -> 0 -> 1，那麼它表示二進制數 01101，也就是 13 。對樹上的每一片葉子，我們都要找出從根到該葉子的路徑所表示的數字。

題解

一：借用層序周遊的思想，用隊列先進先出的結構，隊列中放入節點，以及截止該節點的二進制表示的十進制數（截止其父節點的數*2+目前節點的值）的pair對，當該節點是葉子節點，我們将該數加入結果。

from collections import deque
class Solution(object):
    def sumRootToLeaf(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0 
        q, res = deque(), 0
        q.append((root, root.val))

        while q:
            n = len(q)
            for i in range(n):
                node, v = q.popleft() 
                if not node.left and not node.right:
                    res += v 
                if node.left:
                    q.append((node.left, v * 2 + node.left.val))
                if node.right:
                    q.append((node.right, v * 2 + node.right.val))
        return res

二：DFS，遞歸，尋求遞歸關系，目前結點的二進制和=上一結點的二進制和*2+目前結點的值。

class Solution(object):
    def sumRootToLeaf(self, root):
        if not root:
            return 0 
        return self.dfs(root, 0)

    def dfs(self, root, val):
        if not root:
            return 0
        val = 2 * val + root.val 
        if not root.left and not root.right:
            return val
        return self.dfs(root.left, val) + self.dfs(root.right, val)

538. 把二叉搜尋樹轉換為累加樹

https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

題解

一：回溯，我們想辦法在周遊一個節點之前先周遊完所有比他大的節點，這些節點存在于右子樹中，故先周遊右子樹，在周遊該節點，在周遊左子樹（右->根->左），即從小到大周遊，同時維護一個全局變量，用來記錄累加和，這樣周遊到一個節點，已經周遊過大于他的節點，将全局變量加上目前節點的值即是對應新的根節點的值。dfs傳回的是符合題意的對應目前節點的新的根。

class Solution(object):
    def __init__(self):
        self.res = 0

    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def dfs(root):
            if not root:
                return None, self.res
            new_root = TreeNode(0)
            new_root.right = dfs(root.right)[0]
            self.res += root.val 
            new_root.val = self.res
            new_root.left = dfs(root.left)[0]
            return new_root, self.res
            
            
        if not root:
            return None 
        new_root = dfs(root)[0]
        return new_root

337. 打家劫舍 III

144. 二叉樹的前序周遊

94. 二叉樹的中序周遊

145. 二叉樹的後序周遊

589. N叉樹的前序周遊

590. N叉樹的後序周遊

102. 二叉樹的層序周遊

559. N叉樹的最大深度

1022. 從根到葉的二進制數之和

538. 把二叉搜尋樹轉換為累加樹

繼續閱讀

#每日一題力扣第28題采購方案

【python】：布爾運算

【算法導論】堆排序一、數組轉換成堆二、如何進行堆排序三、堆排序過程四、堆排序時間複雜度

二叉樹三種周遊(先序，中序，後序)----超詳細引入先序周遊後序周遊中序周遊總結

二叉樹的先序、中序、後序周遊總結

對角線周遊LeetCode–對角線周遊

二叉樹及其應用--二叉樹建立

用JS模拟實作二叉樹(含周遊)

資料結構---二叉樹（手動建立及周遊）

樹的基本概念(定義、基本術語、性質)

查找算法之二分查找查找算法之二分查找

LeetCode-110-平衡二叉樹-C語言

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

27. Remove Element(清單)題目代碼

LeetCode OJ Binary Tree Right Side View

leetcode809