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: a=self._inorder(root.left) b=self._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: tem=root.right root.right=root.left root.left=tem self.invertTree(root.left) self.invertTree(root.right) return root
36. 对称二叉树
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: a=self.inorder(root.left) b=self.inorder(root.right) self.max_diam=max(self.max_diam,a+b) return max(a,b)+1 else: return 0 def diameterOfBinaryTree(self, root): self.max_diam = 0 self.inorder(root) return self.max_diam
38. 二叉树的层序遍历
from collections import deque class Solution(object): def levelOrder(self, root): if not root: return [] dq=deque() dq.append(root) ans=root res=[] l=[] while dq : cur=dq.popleft() l.append(cur.val) if cur.left: dq.append(cur.left) if cur.right: dq.append(cur.right) if cur==ans: res.append(l) l=[] if dq: ans=dq[-1] return res
class 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,w+1) self.inorder(root.right,w+1) def levelOrder(self, root): self.res=[] self.inorder(root,0) return self.res
39 将有序数组转换为二叉搜索树
class Solution(object): def create_Tree(self,nums,left,right): if left>right: return None elif left==right: return TreeNode(nums[left]) else: mid=left+(right-left)//2 root=TreeNode(nums[mid]) root.left=self.create_Tree(nums,left,mid-1) root.right=self.create_Tree(nums,mid+1,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: a=self.inorder(root.left) if root.val<=self.ans: return False self.ans=root.val b=self.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"),high=float("inf")): if not node: return True cur=node.val if cur<=low or cur>=high: 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.k=k self.res=None def inorder(node): if node: inorder(node.left) if self.k==1: self.res=node.val self.k-=1 inorder(node.right) inorder(root) return self.res
42. 二叉树的右视图
from collections import deque class Solution(object): def rightSideView(self, root): dq=deque() ans=root if not root: return [] dq.append(root) res=[] while dq: cur=dq.popleft() if cur.left: dq.append(cur.left) if cur.right: dq.append(cur.right) if ans==cur : res.append(cur.val) if dq: ans=dq[-1] return res
43. 二叉树展开为链表
class Solution(object): def flatten(self, root): if root: a=self.flatten(root.left) b=self.flatten(root.right) if not a and not b: return root root.left=None root.right=None if a: root.right=a if b: cur=root while cur.right: cur=cur.right cur.right=b return root return None
44. 从前序与中序遍历序列构造二叉树
class Solution(object): def buildTree(self, preorder, inorder): if len(preorder)>=1: val=preorder[0] for i in range(len(preorder)): if inorder[i]==val: a=self.buildTree(preorder[1:1+i],inorder[0:i]) b=self.buildTree(preorder[1+i:],inorder[i+1:]) break root=TreeNode(val,a,b) return root return None
45. 路径总和 III
class Solution(object): def pathSum(self, root, targetSum): if root: def fun(root,targetSum): if root: res=1 if root.val==targetSum else 0 res+=fun(root.left,targetSum-root.val) res+=fun(root.right,targetSum-root.val) return res return 0 return fun(root,targetSum)+self.pathSum(root.left,targetSum)+self.pathSum(root.right,targetSum) return 0
class Solution(object): def pathSum(self, root, targetSum): self.res=0 mp={} mp[0]=1 def dfs(node,cur_sum): if node: cur_sum+=node.val self.res+=mp.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.res
46. 二叉树的最近公共祖先
class Solution(object): def lowestCommonAncestor(self, root, p, q): if not root or root==p or root==q: return root left=self.lowestCommonAncestor(root.left,p,q) right=self.lowestCommonAncestor(root.right,p,q) if left and right: return root return left if left else right
47. 二叉树中的最大路径和
class Solution(object): def maxPathSum(self, root): self.max=-float("inf") def fun(root): if root: a=max(fun(root.left),0) b=max(fun(root.right),0) if root.val+a+b>self.max: self.max=root.val+a+b return max(a,b)+root.val return 0 fun(root) return self.max
