[leetcode]第十七部分(103-109)

103-Binary Tree Zigzag Level Order Traversal

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树, 返回z字形层次顺序 遍历的节点值(例如, 从左到右,然后下一次从右到左, 接着进行交替).

例如:给定一个二叉树[3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

返回其z字形层次顺序遍历的结果为:

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

解题思路

这一题和上周的题目类似, 只不过加了一个条件: z字形, 分析一下, 针对第n层(从0开始计数), :

  • n%2==0时, 下一层需要从右到左
  • n%2==1时, 下一次需要从左到右

可以根据当前len(total_ans)来进行区分.

代码

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

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        total_ans = [[root.val]]
        stack = [root.left, root.right]
        next_stack = stack
        while len(next_stack) > 0:
            next_stack = list()
            ans = list()
            is_left = True if (len(total_ans) % 2 == 0) else False
            for i in range(len(stack)):
                cur_node = stack[i]
                if cur_node is not None:
                    if is_left:
                        ans.append(cur_node.val)
                    else:
                        ans = [cur_node.val] + ans
                    next_stack.append(cur_node.left)
                    next_stack.append(cur_node.right)

            stack = next_stack
            if len(ans) > 0:
                total_ans.append(ans)
        return total_ans

104-Maximum Depth of Binary Tree

问题难度: ♣

问题描述

给定一个二叉树, 返回其最大的深度.

最大的深度为从更节点到最远的叶子节点的路径中的节点数.

注意: 叶子节点为无孩子的节点.

示例

给定二叉树为:[3,9,20,null,null,15,7].

    3
   / \
  9  20
    /  \
   15   7

返回其深度为depth=3.

解题思路

方法1: 迭代法

和之前的想法类似, 一层一层地遍历, 然后对层数进行叠加, 直到最下面一层为止.

方法2: 递归法

终结条件在于: 当节点为None时,返回0, 否则, 返回max(depth(root.left), depth(root.right)) + 1.

代码

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

class Solution(object):
    def maxDepthIter(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        stack = [root.left, root.right]
        next_stack = stack
        depth = 1
        while len(next_stack) > 0:
            next_stack = list()
            for i in range(len(stack)):
                cur_node = stack[i]
                if cur_node is not None:
                    next_stack.append(cur_node.left)
                    next_stack.append(cur_node.right)
            if len(next_stack) > 0:
                depth += 1
            stack = next_stack
        return depth

    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        if left_depth > right_depth:
            return left_depth + 1
        else:
            return right_depth + 1

105-Construct Binary Tree from Preorder and Inorder Traversal

问题描述: ♣ ♣ ♣

问题描述

给定一个树的前序和中序遍历, 构建二叉树.

注意:
可以假设树中不存在重复.

例如, 给定:

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

返回下面的二叉树

    3
   / \
  9  20
    /  \
   15   7

解题思路

回顾一下前序遍历的概念: 中-左-右
中序遍历的概念: 左-中-右

因此, 对于前序遍历中的元素: 只要是没有添加到树中的, 那么第一位肯定是根节点, 然后我们再基于中序遍历来获取它的左子树和右子树,在中序遍历中, 在根节点左侧的肯定是左子树, 而在根节点右边的肯定是右子树. 当中序数组的长度为0时,说明已经后面已经没有值了, 直接返回None即可.

代码

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

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        def buildChildTree(preorder, inorder):
            if len(inorder) == 0:
                return None
            # pick up the first element as root
            root = preorder[0]
            root_node = TreeNode(root)
            # split the left subtree and right subtree
            root_idx = -1
            for i in range(len(inorder)):
                if inorder[i] == root:
                    root_idx = i
                    break
            preorder.remove(root)
            # recursion
            root_node.left = buildChildTree(preorder, inorder[: root_idx])
            root_node.right = buildChildTree(preorder, inorder[root_idx + 1: ])
            return root_node
        return buildChildTree(preorder, inorder)

106-Construct Binary Tree from Inorder and Postorder Traversal

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树的中序遍历和后序遍历, 还原该二叉树.

注意: 可以假设树中没有重复的节点值.

例如, 给定:

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

返回下面的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解题思路

中序遍历的顺序: 左-中-右

和上题一样, 回顾下后序遍历的顺序: 左-右-中

那么不难看出, 最后一个应该是根节点. 然后我们再基于中序遍历, 划分其左子树和右子树.

接着,是右子树,递归调用;最后是左子树,递归调用.

代码

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

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """

        def buildSubTree(inorder, postorder):
            if len(inorder) == 0:
                return None
            # pick up the last element as the root
            root = postorder[-1]
            root_node = TreeNode(root)
            postorder.remove(root)
            # find the root index to split
            root_idx = -1
            for i in range(len(inorder)):
                if inorder[i] == root:
                    root_idx = i
                    break
            # recursion
            root_node.right = buildSubTree(inorder[root_idx + 1 : ], postorder)
            root_node.left = buildSubTree(inorder[ : root_idx ], postorder)
            return root_node

        return buildSubTree(inorder, postorder)

107-Binary Tree Level Order Traversal II

问题难度: ♣

问题描述

给定一个二叉树, 返回其节点值从下到上的层次遍历(也就是说: 从下到上, 从左到右).

例如:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历结果如下:

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

解题思路

这题和之前层次遍历的问题类似, 只不过在返回之前要先做一遍逆序.

代码

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

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        cur_nodes = [root]
        total_node_vals = list()
        while len(cur_nodes) > 0:
            next_nodes = list()
            node_vals = list()
            for i in range(len(cur_nodes)):
                cur_node = cur_nodes[i]
                if cur_node is not None:
                    node_vals.append(cur_node.val)
                    next_nodes.append(cur_node.left)
                    next_nodes.append(cur_node.right)
            cur_nodes = next_nodes
            if len(node_vals) > 0:
                total_node_vals.append(node_vals)
        ret_list = list()
        for i in range(len(total_node_vals)):
            ret_list.append(total_node_vals[len(total_node_vals)-i-1])
        return ret_list

108-Convert Sorted Array to Binary Search Tree

问题难度: ♣

问题描述

给定一个元素升序排列的数组, 将其转化为一个高度均衡的检索二叉树.

在这个问题中, 一个高度均衡的二叉树指的是: 每个节点的两个子树的深度永远不会超过1.

示例

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是 [0,-3,9,-10,null,5],可以表示为下面高度均衡的二叉树:


0 / \ -3 9 / / -10 5

解题思路

回顾一下检索二叉树的概念: 左子树的值永远小于根节点的值, 根节点的值永远小于右子树的值.

针对高度均衡, 结合检索二叉树的概念, 我们不难知道: 针对某个数组, 根节点一点位于中间, 其左边的值肯定在其左子树中,而右边的值肯定在其右子树上.直到数组中不再有元素, 则返回None.

代码

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

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 0:
            return None
        mid = len(nums) / 2
        root_node = TreeNode(nums[mid])
        root_node.left = self.sortedArrayToBST(nums[ : mid])
        root_node.right = self.sortedArrayToBST(nums[mid + 1:])
        return root_node

109-Convert Sorted List to Binary Search Tree

问题难度: ♣ ♣ ♣

问题描述

给定一个元素升序排列的链表, 将其转化为一个高度均衡的检索二叉树.

在这个问题中, 一个高度均衡的二叉树指的是: 每个节点的两个子树的深度永远不会超过1.

示例

给定有序链表: [-10,-3,0,5,9],

一个可能的答案是 [0,-3,9,-10,null,5],可以表示为下面高度均衡的二叉树:


0 / \ -3 9 / / -10 5

解题思路

将问题转化为已知问题即可求解…先把链表转化为有序数组, 再按照上一题的思路将其转化为检索二叉树即可.

但是, 很明显这道题目并不是想考察这个…根据上一题的分析,我们知道这个问题的核心就是: 获取到中间节点, 然后再分别向两边递归.

在这里, 我们使用两个指针, midright, 两个指针同时向右移动, 但是, 每一次, mid只移动一步, 而right则移动两步,直到right移动到末尾为止,此时mid将指向中间节点.(当然, 在mid移动之前, 得判断下right.next是否为None,再决定是否前移.)

代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

class Solution(object):
    def sortedListToBSTRec(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        nums = []
        while head is not None:
            nums.append(head.val)
            head = head.next
        def sortedArrayToBST(nums):
            if len(nums) == 0:
                return None
            mid = len(nums) / 2
            root_node = TreeNode(nums[mid])
            root_node.left = sortedArrayToBST(nums[:mid])
            root_node.right = sortedArrayToBST(nums[mid+1:])
            return root_node
        return sortedArrayToBST(nums)

    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        if head is None:
            return None
        def findMidEle(head):
            pre = None
            mid = head
            right = head
            while right is not None and right.next is not None:
                pre = mid
                mid = mid.next
                right = right.next.next
            if pre is not None:
                pre.next = None
            return mid
        mid = findMidEle(head)
        root_node = TreeNode(mid.val)
        if head == mid:
            return root_node
        root_node.left = self.sortedListToBST(head)
        root_node.right = self.sortedListToBST(mid.next)
        return root_node
打赏

mickey

记录生活,写给几十年后的自己。