asp.net 网站开发 实战,推广网站的作用,网店代运营公司哪家强,视频剪辑培训比较有名的学校持续更新... github链接#xff1a;https://github.com/x2mercy/Leetcode_Solution 为什么括号200道呢#xff01;因为准备按照200道这样的周期刷#xff0c;每200道刷两遍#xff0c;第一遍按难度刷#xff0c;第二遍按类别刷#xff01; 先整理binarytree这一类别也是因…持续更新... github链接https://github.com/x2mercy/Leetcode_Solution 为什么括号200道呢因为准备按照200道这样的周期刷每200道刷两遍第一遍按难度刷第二遍按类别刷 先整理binarytree这一类别也是因为在刷题的过程中由于没有系统的算法基础这类题目算是遇到的比较大的障碍。 下面按照题目难度来说 —————————————————————————————————————————————————————————————————————————————————————— EASY 1. Same Tree Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. 这是我做的第一道二叉树的题目。 一开始的思路是二叉树的遍历找到的资料http://blog.csdn.net/bone_ace/article/details/46718683 主要说了树的构造和几种遍历方式 所以第一种方法是用层次遍历做的代码如下 # this solution is Time Limit Exceeded
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def isSameTree(self, p, q)::type p: TreeNode:type q: TreeNode:rtype: boolresult1[]result1.append(p.val)while p:if p.left!None:result1.append(p.left)if p.right!None:result1.append(p.right)result2[]result2.append(q.val)while q:if q.left!None:result1.append(q.left)if q.right!None:result1.append(q.right)resultcmp(result1,result2)if result0:return Trueelse:return False 满心欢喜的以为可以过但是却报了time limit exceed的错误于是开始找第二种方法 上代码 # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def isSameTree(self, p, q)::type p: TreeNode:type q: TreeNode:rtype: boolif pNone and qNone:return Trueif pNone or qNone:return Falseif p.valq.val:return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)return False 这种做法写完之后呢。。emmmm觉得自己上一种方法简直是智障儿童 这种方法很简单呐重点是用了递归。递归真是一种逻辑简洁的好东西利用递归比较子树的各个节点是否相同。 2. Symmetric Tree: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). 先上代码 # recursive answer
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def isSymmetric(self, root)::type root: TreeNode:rtype: boolif rootNone:return Truereturn self.isMirror(root.left,root.right)def isMirror(self,p,q):if pNone and qNone:return Trueif pNone or qNone:return Falsereturn p.valq.val and self.isMirror(p.left,q.right) and self.isMirror(p.right,q.left) 这道题的重点在于调用了另一个函数因为需要比较是否对称的本质是比较左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点是否相等所以需要调用IsMirror函数可以接收两个argisMirror返回的boolean值主要由节点值是否相等以及下个节点是否对称来决定所以这里用了递归。 注意用了递归就一定要有递归停止的条件不能无限循环下去 3. Maximum Depth of Binary Tree Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 这道题算法很经典mark一下可以用在很多二叉树的题目中。 上代码 #iterator
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def maxDepth(self, root)::type root: TreeNode:rtype: intif rootNone:return 0DLself.maxDepth(root.left)DRself.maxDepth(root.right)return max(DL,DR)1 后面还有一道求最短路径的题目和这个做法类似 主要也是用了递归最后返回的时候注意要1因为返回的是节点数 4. Binary Tree Level Order Traversal II Given a binary tree, return the bottom-up level order traversal of its nodes values. (ie, from left to right, level by level from leaf to root). # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def levelOrderBottom(self, root)::type root: TreeNode:rtype: List[List[int]]if rootNone:return []pcollections.deque()p.append((root,0))result[]while p:node,indexp.popleft()if indexlen(result)-1:result.append([node.val])else:result[index].append(node.val)if node.left:p.append((node.left,index1))if node.right:p.append((node.right,index1))result.reverse()return result 这里本来想用queue但是发现了一个很神奇的东西:deque学疏才浅。。是python标准库里的一项直接from collections import deque或者像我这样collections.deque就可以用了。 它的好处在于它可以提供类似于list的操作比如append什么的但是不同的是可以popleft操作使第一位元素pop出来。参考http://blog.csdn.net/qins_superlover/article/details/44338415 这一种操作对解决二叉树问题提供了很大的帮助比如这道题 这道题是让我们把整个二叉树倒过来返回从最底层到最上层的节点给的例子是这样的 于是我们知道了在append节点时需要注意把它的index也append进去这样便于后面判断是不是同一层的节点。 因为父节点下面的两个子节点的index是一样的所以在append左边节点之后会出现len(result-1是大于右边节点index的这时直接把右边节点append到result[index]中等于是个多维array 最后再reverse一下返回搞定 5. Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending order, convert it to a height balanced BST. 这里第一次遇到平衡二叉树所谓平衡二叉树要满足几个条件它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树 所以又要用到递归 上代码 # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def sortedArrayToBST(self, nums)::type nums: List[int]:rtype: TreeNodeif nums[]:return Nonemidlen(nums)//2rootTreeNode(nums[mid])root.leftself.sortedArrayToBST(nums[:mid])root.rightself.sortedArrayToBST(nums[mid1:])return root 其实这道题很简单核心就是要找到根节点而因为是sortedarray所以要找根节点就直接找中间的那个元素为了避免麻烦用了//表示取商的整数部分 然后分别对左子树和右子树用递归这里的nums[:mid]和nums[mid1:]表示nums从下标为0到mid不包括midnums从下标mid1到最后 6. Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def isBalanced(self, root)::type root: TreeNode:rtype: boolif rootNone:return TrueDLself.depth(root.left)DRself.depth(root.right)if DL-DR-1 or DL-DR1:return Falsereturn self.isBalanced(root.left) and self.isBalanced(root.right)def depth(self,node):if nodeNone:return 0DLself.depth(node.left)DRself.depth(node.right)return max(DL,DR)1 这里要注意的是判断是否为平衡二叉树需要考虑一个节点左右子树是否都为平衡二叉树所以在返回时需要用and来实现 调用了depth函数前面说了这个函数很经典很常用 然后就是在比较高度时要注意-1的情况 7. Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def minDepth(self, root)::type root: TreeNode:rtype: intif rootNone:return 0DLself.minDepth(root.left)DRself.minDepth(root.right)dmin(DL,DR)Dmax(DL,DR)if DL0 or DR0:return D1else:return d1 看吧这个算法真的很常用 但是要注意的是如果某一子树路径为0 则取左右子树中最大的那个如果都不为0则取左右子树中最小的那个 8. Path Sum: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution(object):def hasPathSum(self, root, sum)::type root: TreeNode:type sum: int:rtype: boolif rootNone:return Falseif root.rightNone and root.leftNone and root.valsum:return Truesumsum-root.valreturn self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum) 这道题最开始想复杂了一直在想用deque()然后一个一个节点加但其实不用cheat了一下看了dicuss发现了机智的做法
只需要依次比较每个节点比较完之后sum减去这个节点然后比较下一个左或者右直到sum某个节点则返回true
否则返回false重点在于每次都需要sum减去这个节点值这样如果剩下的节点值等于这个数并且它没有左右子树则返回true ———————————————————————————————————————————————————————————————————————————————————— 转载于:https://www.cnblogs.com/x1mercy/p/7802167.html
