33-47 树

33. 二叉树的中序遍历class Solution(object): def inorderTraversal(self, root): res [] self._inorder(root, res) return res def _inorder(self, node, res): if node: self._inorder(node.left, res) res.append(node.val) self._inorder(node.right, res)34. 二叉树的最大深度class Solution(object): def _inorder(self,root): if root: aself._inorder(root.left) bself._inorder(root.right) return max(a,b)1 else: return 0 def maxDepth(self, root): return self._inorder(root)35. 翻转二叉树class Solution(object): def invertTree(self, root): if root: temroot.right root.rightroot.left root.lefttem self.invertTree(root.left) self.invertTree(root.right) return root36. 对称二叉树class Solution(object): def judge(self,left,right): if left and right: if left.val!right.val: return False return self.judge(left.right,right.left) and self.judge(left.left,right.right) else: if left or right: return False return True def isSymmetric(self, root): return self.judge(root.left,root.right)37. 二叉树的直径class Solution(object): def inorder(self,root): if root: aself.inorder(root.left) bself.inorder(root.right) self.max_diammax(self.max_diam,ab) return max(a,b)1 else: return 0 def diameterOfBinaryTree(self, root): self.max_diam 0 self.inorder(root) return self.max_diam38. 二叉树的层序遍历from collections import deque class Solution(object): def levelOrder(self, root): if not root: return [] dqdeque() dq.append(root) ansroot res[] l[] while dq : curdq.popleft() l.append(cur.val) if cur.left: dq.append(cur.left) if cur.right: dq.append(cur.right) if curans: res.append(l) l[] if dq: ansdq[-1] return resclass Solution(object): def inorder(self,root,w): if root: if len(self.res)w: self.res.append([root.val]) else: self.res[w].append(root.val) self.inorder(root.left,w1) self.inorder(root.right,w1) def levelOrder(self, root): self.res[] self.inorder(root,0) return self.res39 将有序数组转换为二叉搜索树class Solution(object): def create_Tree(self,nums,left,right): if leftright: return None elif leftright: return TreeNode(nums[left]) else: midleft(right-left)//2 rootTreeNode(nums[mid]) root.leftself.create_Tree(nums,left,mid-1) root.rightself.create_Tree(nums,mid1,right) return root def sortedArrayToBST(self, nums): if len(nums)0: return None return self.create_Tree(nums,0,len(nums)-1)40. 验证二叉搜索树class Solution(object): def inorder(self,root): if root: aself.inorder(root.left) if root.valself.ans: return False self.ansroot.val bself.inorder(root.right) return a and b else: return True def isValidBST(self, root): self.ans-float(inf) return self.inorder(root)class Solution(object): def isValidBST(self, root): def judge(node,low-float(inf),highfloat(inf)): if not node: return True curnode.val if curlow or curhigh: return False return judge(node.left,low,cur) and judge(node.right,cur,high) return judge(root)41. 二叉搜索树中第 K 小的元素class Solution(object): def kthSmallest(self, root, k): self.kk self.resNone def inorder(node): if node: inorder(node.left) if self.k1: self.resnode.val self.k-1 inorder(node.right) inorder(root) return self.res42. 二叉树的右视图from collections import deque class Solution(object): def rightSideView(self, root): dqdeque() ansroot if not root: return [] dq.append(root) res[] while dq: curdq.popleft() if cur.left: dq.append(cur.left) if cur.right: dq.append(cur.right) if anscur : res.append(cur.val) if dq: ansdq[-1] return res43. 二叉树展开为链表class Solution(object): def flatten(self, root): if root: aself.flatten(root.left) bself.flatten(root.right) if not a and not b: return root root.leftNone root.rightNone if a: root.righta if b: curroot while cur.right: curcur.right cur.rightb return root return None44. 从前序与中序遍历序列构造二叉树class Solution(object): def buildTree(self, preorder, inorder): if len(preorder)1: valpreorder[0] for i in range(len(preorder)): if inorder[i]val: aself.buildTree(preorder[1:1i],inorder[0:i]) bself.buildTree(preorder[1i:],inorder[i1:]) break rootTreeNode(val,a,b) return root return None45. 路径总和 IIIclass Solution(object): def pathSum(self, root, targetSum): if root: def fun(root,targetSum): if root: res1 if root.valtargetSum else 0 resfun(root.left,targetSum-root.val) resfun(root.right,targetSum-root.val) return res return 0 return fun(root,targetSum)self.pathSum(root.left,targetSum)self.pathSum(root.right,targetSum) return 0class Solution(object): def pathSum(self, root, targetSum): self.res0 mp{} mp[0]1 def dfs(node,cur_sum): if node: cur_sumnode.val self.resmp.get(cur_sum-targetSum,0) mp[cur_sum]mp.get(cur_sum,0)1 dfs(node.left,cur_sum) dfs(node.right,cur_sum) mp[cur_sum]-1 else: return dfs(root,0) return self.res46. 二叉树的最近公共祖先class Solution(object): def lowestCommonAncestor(self, root, p, q): if not root or rootp or rootq: return root leftself.lowestCommonAncestor(root.left,p,q) rightself.lowestCommonAncestor(root.right,p,q) if left and right: return root return left if left else right47. 二叉树中的最大路径和class Solution(object): def maxPathSum(self, root): self.max-float(inf) def fun(root): if root: amax(fun(root.left),0) bmax(fun(root.right),0) if root.valabself.max: self.maxroot.valab return max(a,b)root.val return 0 fun(root) return self.max