LeetCode Solutions – 二元樹與中序遍歷 Leetcode 94, 100 ,101 Binary Tree Inorder Traversal

二元樹是一個常見的數據結構,結構像是下列

在每一個節點會存三件東西,一個是節點本身的值,另外兩個是存指向左右節點的位置,舉例來說,在上面圖的根節點(最上面的點),本身的值是1,分別有兩條線指向左右兩個節點,當然節點也有可能不存在。

在python上面,我們可以很簡單的實作節點出來,如下

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

這邊我們定義一個物件叫做TreeNode(樹節點),每一個節點有三個屬性可以存,val、left以及right,有了節點物件後,我們就可以利用節點物件建構出一個二元樹魯。

但有了二元樹這個數據結構後,我們要如何有效率的搜尋整個樹的結構?

常見的有兩種搜尋方式,一個是深度優先搜尋,一個是廣度優先搜尋。

深度優先便是沿著一個分支往深處探索,然後慢慢探索完全部節點。

廣度搜尋便是對每一層進行尋找

這邊要分享的Leetcode題目便是深度搜尋的一個例子- 中序遍歷

題目如下

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

# 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 is None:
            return []
        stack = [root]
        res = []
        while len(stack) > 0:
            curr = stack.pop()
            if not isinstance(curr, TreeNode):
                res.append(curr)
                continue
            if curr.right is not None:
                stack.append(curr.right)
            stack.append(curr.val)
            if curr.left is not None:
                stack.append(curr.left)
        return res
            

用同樣的思路可以來解決100題的判斷是否為同一顆樹,可以對兩棵樹進行節點搜尋,發現有節點有不同的值,回傳False,如果都一樣且兩棵樹的節點數一致則回傳True

# 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:
        if (p is None) and (q is None):
            return True
        if (p is None) or (q is None):
            return False
        if p.val != q.val:
            return False
        
        stack_p = [p]
        stack_q = [q]
        while (len(stack_p) > 0) and (len(stack_q) > 0):
            curr_p = stack_p.pop()
            curr_q = stack_q.pop()
            if type(curr_p) != type(curr_q):
                return False
            if not isinstance(curr_p, TreeNode):
                if curr_p != curr_q:
                    return False
                continue
            if curr_p.right is not None:
                stack_p.append(curr_p.right)
            if curr_q.right is not None:
                stack_q.append(curr_q.right)
            stack_p.append(curr_p.val)
            stack_q.append(curr_q.val)
            if curr_p.left is not None:
                stack_p.append(curr_p.left)
            if curr_q.left is not None:
                stack_q.append(curr_q.left)
        if len(stack_p) != len(stack_q):
            return False
        return True
        
        

Share

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *