Leetcode 98. 驗(yàn)證二叉樹

給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。
假設(shè)一個(gè)二叉搜索樹具有如下特征：
節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入:
2
/
1 3
輸出: true

解題思路：自頂向下，確定每個(gè)節(jié)點(diǎn)的取值范圍，然后遞歸。

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.bfs(root, -float('inf'), float('inf'))
    def bfs(self, root, mini, maxi):
        if root == None:
            return True
        if root.val < mini or root.val > maxi:
            return False
        return self.bfs(root.left, mini, root.val-1) and self.bfs(root.right, root.val+1, maxi)

Leetcode 101. 對(duì)稱二叉樹

給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對(duì)稱的。
1
/
2 2
/ \ /
3 4 4 3
但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱的:
1
/
2 2
\
3 3
說(shuō)明:
如果你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題，會(huì)很加分。

解題思路：要判斷兩棵樹是不是對(duì)稱樹，需要：1.根節(jié)點(diǎn)相同，2. 左邊的左子樹和右邊的右子樹相同，3. 左邊的右子樹和右邊的左子樹相同。

圖片.png

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root ==None:
            return True
        return self.dfs(root.left, root.right)

    def dfs(self, p, q):
        if p == None or q ==None:
            return not p and not q
        return p.val == q.val and self.dfs(p.left, q.right) and self.dfs(p.right, q.left)

Leetcode 94. 二叉樹的中序遍歷（迭代法）

給定一個(gè)二叉樹，返回它的中序 遍歷。
示例:
輸入: [1,null,2,3]
1

2
/
3
輸出: [1,3,2]
進(jìn)階: 遞歸算法很簡(jiǎn)單，你可以通過(guò)迭代算法完成嗎？

解題思路：

圖片.png

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        p = root
        
        while p or len(stack) != 0:
            while p:
                stack.append(p)
                p = p.left
            p = stack[-1]
            stack = stack[:-1]
            res.append(p.val)
            p = p.right
        return res

Leetcode 105. 從前序遍歷和中序遍歷構(gòu)造二叉樹

根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/
9 20
/
15 7

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(preorder) == 0:
            return None
        head = TreeNode(preorder[0])
        mid = inorder.index(head.val)
        head.left = self.buildTree(preorder[1 : mid + 1], inorder[0 : mid])
        head.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
        return head

Leetcode 102. 二叉樹的層次遍歷

給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值。 （即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return None
        queue = [root]
        result = []
        
        while queue:
            temp_list = []
            length = len(queue)
            for i in range(length):
                temp = queue.pop(0)
                temp_list.append(temp.val)
                if temp.left:
                    queue.append(temp.left)
                if temp.right:
                    queue.append(temp.right)
            result.append(temp_list)
        return result

Leetcode 236. 二叉樹的最近公共祖先

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == None or p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        if not left:
            return right
        if not right:
            return left
        return None