leetcode解题报告-树

本贴最后更新于 2149 天前,其中的信息可能已经水流花落

树是最常考察的数据结构。由于树的定义是递归的(树的子树也是树),因此大部分的树的问题,如求树的最大深度、判定树是否平衡、共同祖先等,可以由递归进行求解,这也是最简单最直接的方式。

但是,通常面试官都希望你答出非递归解法。如前中后序的非递归解法都是借助栈进行实现(利用栈先进后出的特性,结合进出栈的时机)。先序列遍历和中序遍历对栈的操作相同,栈顶左子一直进栈直到最左下,弹栈,右子进栈。然后循环操作即可。唯一不同是先序遍历是在进栈前访问,中序遍历是在弹栈的时候访问。后序遍历,进栈的顺序为根右左,由于栈的特性会使出栈时为左右根。进栈时需标记当前节点左右子是否已经进栈了。树的按层次遍历是借助队列先进先出的特性实现的。

对应的树的遍历方法有 DFS 和 BFS,DFS 和先序遍历是一致的。BFS 和按层次遍历是一致的。

另外,在解决树问题的时候需要充分利用该树的特性,如二叉搜索树,完全二叉树的特性。


##94. Binary Tree Inorder Traversal (中序遍历)

  • 难度:Medium

  • 题意:
    给一个二叉树,返回该树的中序遍历。

  • 思路 1:
    中序遍历即左中右,思路 1 先使用递归实现,递归是最方便书写且最容易理解的,因为树本身就是递归定义的。递归访问左子树,输出根,递归访问右子树。

  • 代码 1:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[]}
          res=[]
          def inorderTraversal(self, root):
              self.res=[]
              self.reduce(root)
              return self.res
          def reduce(self,root):
              if root and root.left:self.reduce(root.left)
              if root:self.res.append(root.val)
              if root and root.right:self.reduce(root.right)
    
  • 思路 2:
    通常面试中,面试官肯定不会想看到上面的解法,一般会让用非递归实现。中序遍历的非递归实现是借助栈实现的。将根节点入栈,若栈顶节点存在左子树,则左子树进栈,否则出栈并添加到结果中。

      class Solution:
          # @param {TreeNode} root
          # @return {integer[]}
          def inorderTraversal(self, root):
              result = []
              stack = []
              if not root: return result
              stack.append(root)
              while stack:
                  if stack[-1].left:
                      stack.append(stack[-1].left)
                      stack[-2].left = None
                  else:
                      node = stack.pop(-1)
                      result.append(node.val)
                      if node.right:
                          stack.append(node.right)
              return result
    

##96. Unique Binary Search Trees (BST)

  • 难度:Medium

  • 题意:
    给定整数 n,求出以 1...n 作为节点,有多少种结构不同的二叉搜索树

  • 思路:
    每个节点都可以作为跟,对于每个节点来说,可以构成二叉树的总类型数=左子树总类型数*右子树总类型数。因此可以采用 dp 解决。

  • 代码:

      class Solution:
          # @param {integer} n
          # @return {integer}
          def numTrees(self, n):
              dp = [1,1]
              for i in range(2,n+1):
                  dp.append(0)
                  for j in range(0,i):
                      dp[i] += dp[j]*dp[i-j-1]
              return dp[n]
    

##95. Unique Binary Search Trees II (BST)

  • 难度:Medium

  • 题意:
    给定数字 n,要求用数字 1 到 n 构造出所有不同的二叉搜索树

  • 思路:
    二叉搜索树,左子树 < 根 < 右子树。这也是我们构造的思路。对于(left,right),我们循环遍历设置 i 为根,则左子树的范围是(left,i-1),右子树的范围是(i+1,right)。递归构造左子树和右子树,返回所有可能的根。

  • 代码:

      class Solution:
          # @param {integer} n
          # @return {TreeNode[]}
          def generateTrees(self, n):
              return self.creatTrees(1,n)
    
          def creatTrees(self,start,end):
              result = []
              if start>end:
                  result.append(None)
                  return result
              for i in range(start,end+1):
                  lefts = self.creatTrees(start,i-1)
                  rights = self.creatTrees(i+1,end)
                  for left in lefts:
                      for right in rights:
                          root = TreeNode(i)
                          root.left = left
                          root.right = right
                          result.append(root)
              return result
    

##98. Validate Binary Search Tree (BST)

  • 难度:Medium

  • 题意:
    给定一个二叉树,检查其是否而二叉搜索树。

  • 思路:
    二叉搜索树的特点是 左 < 根 < 右,因此,对二叉搜索数进行中序遍历,输出的结果即为正序。

  • 代码:

      class Solution:
          def LDR(self, root):
              if root != None:
                  if root.left != None:
                      self.LDR(root.left)
                  self.tree.append(root.val)
                  if root.right != None:
                      self.LDR(root.right)
    
          # @param {TreeNode} root
          # @return {boolean}
          def isValidBST(self, root):
              self.tree=[]
              self.LDR(root)
              i=0
              while i<len(self.tree)-1:
                  if self.tree[i] >= self.tree[i+1]:
                      return False
                  i+=1
              return True
    

##99. Recover Binary Search Tree (BST)

  • 难度:Hard

  • 题意:
    二叉搜索树中有两个节点被调换了位置,在不改变数据结构的基础上还原二叉搜索树。要求在 o(n)空间复杂度内解决。

  • 思路:
    这道题有一种巧妙的思路利用了递归中序遍历的递归和回溯过程。这里使用 pre 来记录被遍历的前一个节点。中序遍历的递归方法是,递归访问左子树到最左下端,然后回溯,再对右子进行递归。回溯的时候,pre 是当前访问节点的左子,再向右递归时,pre 是当前右子的根,因此总有 pre<root 成立,若不成立则为被调换的点。

  • 思路:

      class Solution(object):
          def recoverTree(self, root):
              """
              :type root: TreeNode
              :rtype: void Do not return anything, modify root in-place instead.
              """
              self.mis1,self.mis2,self.pre=None,None,None
              self.traval(root)
              if self.mis1 and self.mis2:
                  self.mis1.val,self.mis2.val=self.mis2.val,self.mis1.val
    
          def traval(self,root):
              if not root:return
              if root.left:self.traval(root.left)
              if self.pre and root.val<self.pre.val:
                  if not self.mis1:
                      self.mis1=self.pre
                  self.mis2=root
              self.pre = root
              if root.right:self.traval(root.right)
    

##100. Same Tree (递归)

  • 难度:Easy

  • 题意:
    给定两个二叉树,验证这两个树是否相等。当且仅当这两棵树结构相同且每个节点值相同时,才认为是相等。

  • 思路:
    两颗树相同,当且仅当,根的值相等,且左子树相等,右子树相等。因此,可以用递归方便地求解。

  • 代码:

      class Solution:
          # @param {TreeNode} p
          # @param {TreeNode} q
          # @return {boolean}
          def isSameTree(self, p, q):
              if not p and not q: return True
              elif (p and not q) or (q and not p) or p.val != q.val: return False
              else: return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
    

##101. Symmetric Tree (递归)

  • 难度:Easy

  • 题意:
    给定一棵二叉树,检查是否为镜像对称。

  • 思路:
    一棵树是否为镜像,取决与左子树和右子树是否镜像对称。左子树和右子树是否镜像对称,取决于左子树的左子树和右子树的右子树是否镜像对称,且,左子树的右子树和右子树的左子树是否镜像对称。因此用递归可以求解。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {boolean}
          def isSymmetric(self, root):
              if not root:return True
              return self.isSame(root.left,root.right)
    
          def isSame(self, p, q):
              if not p and not q: return True
              elif (p and not q) or (q and not p) or p.val != q.val: return False
              else: return self.isSame(p.left,q.right) and self.isSame(p.right,q.left)
    

##102. Binary Tree Level Order Traversal (按层次遍历)

  • 难度:Easy

  • 题意: 
    给定一棵二叉树,返回其按层次遍历的节点值序列。输出将同一层次放在同一列表中。

  • 思路:
    树的按层次遍历借助队列完成,将根节点入队。若队列中有节点,弹出出队头,并把队头节点的所有子节点添加到队尾。由于题目要求把同一层的节点放在同一列表中,因此我们的数据结构是 levels[[]],对应的操作是,遍历每一层时,创建一个新的 newlevel[],访问 levels 列表中最后一层的所有节点,并添加到每个节点的子节点到 newlevel 中,最后再把 newlevel 添加到 levels 中。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[][]}
          def levelOrder(self, root):
              if not root :return []
              levels = [[root]]
              values = [[root.val]]
              for level in levels:
                  newLevel = []
                  newValue = []
                  for node in level:
                      if node.left:
                          newLevel.append(node.left)
                          newValue.append(node.left.val)
                      if node.right:
                          newLevel.append(node.right)
                          newValue.append(node.right.val)
                  if newLevel:
                      levels.append(newLevel)
                      values.append(newValue)
              return values
    

##103. Binary Tree Zigzag Level Order Traversal (按层次遍历)

  • 难度:Medium

  • 题意:
    给定一棵二叉树,按照 Z 字形遍历树的节点。

  • 思路:
    该道题其实和 102. Binary Tree Level Order Traversal 是一样的,都是按层次遍历,只是在输出时,按 z 字形输出即可。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[][]}
          def zigzagLevelOrder(self, root):
              values = self.levelOrder(root)
              for i in range(1,len(values),2):
                  values[i].reverse()
              return values
    

##107. Binary Tree Level Order Traversal II

  • 难度:Easy

  • 题意:
    给定一棵二叉树,要求自底向上按层次遍历。

  • 思路:
    还是使用队列辅助进行按层次遍历,思路上和普通按层次遍历没有什么区别。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[][]}
          def levelOrderBottom(self, root):
              if not root :return []
              levels = [[root]]
              values = [[root.val]]
              for level in levels:
                  newLevel = []
                  newValue = []
                  for node in level:
                      if node.left:
                          newLevel.append(node.left)
                          newValue.append(node.left.val)
                      if node.right:
                          newLevel.append(node.right)
                          newValue.append(node.right.val)
                  if newLevel:
                      levels.append(newLevel)
                      values.insert(0,newValue)
              return values
    

##104. Maximum Depth of Binary Tree (最大深度)

  • 难度:Medium

  • 题意:
    给定一棵二叉树,求其最大深度。

  • 思路:
    最简单的想法,一棵树的最大深度=max(左子树的最大深度,右子树的最大深度)+1。使用递归即可快速求解。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer}
          def maxDepth(self, root):
              return 0 if not root else 1+max(self.maxDepth(root.left),self.maxDepth(root.right))
    

  • 思路 2:
    面试官肯定会问,还有非递归的解法吗?这里非递归的解法也非常简单,就是深度优先遍历(先序遍历)。深度优先遍历的非递归解法是借助栈来实现的,
    1. 跟节点入栈
    2. 循环将栈顶的左子入栈,直到无左子
    3. 弹出栈顶,将其右子入栈
    4. 循环 2 和 3
      因此可以看出,栈的深度就是树的深度。
      代码这里就不给出了。

##111. Minimum Depth of Binary Tree (最小深度)

  • 难度:Easy

  • 题意:
    求给定二叉树的最小深度

  • 思路:
    树最小深度 = min(左子最小深度,右子最小深度)+1,递归可求解。当然也可以用按层次遍历求解。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer}
          def minDepth(self, root):
              if not root:return 0
              if not root.left and root.right:return 1+self.minDepth(root.right)
              if not root.right and root.left:return 1+self.minDepth(root.left)
              return 1+min(self.minDepth(root.left),self.minDepth(root.right))
    

##105. Construct Binary Tree from Preorder and Inorder Traversal (先序遍历、中序遍历)

  • 难度:Medium

  • 题意:
    给定一个先序遍历序列和中序遍历序列,要求还原这棵树。

  • 思路:
    先弄清楚先序遍历是根左右,中序遍历是左根右。因此,根据先序遍历可以将中序遍历划分为左右两段,分别代表左子树和右子树。如此递归可以求解。

  • 代码:

      class Solution:
          # @param {integer[]} preorder
          # @param {integer[]} inorder
          # @return {TreeNode},
          def buildTree(self, preorder, inorder):
              if not inorder:return None
              n = preorder[0]
              i = inorder.index(n)
              preorder.remove(n)
              root = TreeNode(n)
              root.left = self.buildTree(preorder,inorder[:i])
              root.right = self.buildTree(preorder,inorder[i+1:])
              return root
    

##106. Construct Binary Tree from Inorder and Postorder Traversal (中序遍历、后序遍历)

  • 难度:Medium

  • 题意:
    给定一棵树的中序和后序遍历的序列,要求还原这棵树。

  • 思路:
    中序遍历是左根右,后序遍历是左右根。因此可以根据后序遍历将中序遍历划分为左右两端,分别代表左子树和右子树,使用递归可以还原整棵树。

  • 代码:

      class Solution:
          # @param {integer[]} inorder
          # @param {integer[]} postorder
          # @return {TreeNode}
          def buildTree(self, inorder, postorder):
              if not inorder:return None
              n = postorder[-1]
              i = inorder.index(n)
              postorder.remove(n)
              root = TreeNode(n)
              root.right = self.buildTree(inorder[i+1:],postorder)
              root.left = self.buildTree(inorder[:i],postorder)
              return root
    

##144. Binary Tree Preorder Traversal(先序遍历)

  • 难度:Medium

  • 题意:
    给定一棵二叉树,返回其先序遍历序列。

  • 思路:
    先序遍历的顺序为:根左右。先序遍历和深度优先遍历类似,采用栈实现。若栈的操作顺序是,根出栈,根右子入栈,根左子入栈。则循环出栈的时候就为根左右的顺序了。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[]}
          def preorderTraversal(self, root):
              result=[]
              stack=[]
              if not root:return result
              stack.append(root)
              while stack:
                  head = stack.pop(-1)
                  result.append(head.val)
                  if head.right:
                      stack.append(head.right)
                  if head.left:
                      stack.append(head.left)
              return result
    

##145. Binary Tree Postorder Traversal (后序遍历)

  • 难度:Medium

  • 题意:
    给定一棵二叉树,返回其后序遍历序列。

  • 思路:
    后序遍历的顺序为:左右根。后序遍历也是借助栈来实现。后序遍历的栈操作顺序为,根入栈。栈顶的右子入栈,标记栈顶的右子已经入栈,栈顶的左子入栈,标记栈顶的左子入栈。当栈顶的左右子均以入过栈,栈顶弹出,否则,重复刚才的操作。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[]}
          def postorderTraversal(self, root):
              result=[]
              stack=[]
              if not root:return result
              stack.append(root)
              while stack:
                  top = stack[-1]
                  if not top.left and not top.right:
                      result.append(top.val)
                      stack.pop(-1)
                  else:
                      if top.right:
                          stack.append(top.right)
                          top.right=None
                      if top.left:
                          stack.append(top.left)
                          top.left=None
              return result
    

##108. Convert Sorted Array to Binary Search Tree (二叉搜索树)

  • 难度:Medium

  • 题意:
    给定一个正序数组,建立对应的二叉搜索树。

  • 思路:
    找到中位数作为根节点,左侧为左子树,右侧为右子树。递归建立即可。

  • 代码:

      class Solution:
          # @param {integer[]} nums
          # @return {TreeNode}
          def sortedArrayToBST(self, nums):
              if not nums: return None
              mid = len(nums)//2
              root = TreeNode(nums[mid])
              root.left = self.sortedArrayToBST(nums[:mid])
              root.right = self.sortedArrayToBST(nums[mid+1:])
              return root
    

##110. Balanced Binary Tree (平衡二叉树)

  • 难度:Easy

  • 题意:
    给定一棵二叉树,检查是否为平衡二叉树

  • 思路:
    一棵树为平衡二叉树的条件是,abs(左子树最大高度-右子树最大高度)<2,且左子树平衡且右子树平衡。树最大高度递=(左子树最大高度,右子树最大高度)+1。用递归的方法从定义出发可以解决。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {boolean}
          def isBalanced(self, root):
              if not root:return True
              return abs(self.maxDepth(root.left)-self.maxDepth(root.right))<2 and self.isBalanced(root.left) and self.isBalanced(root.right)
          def maxDepth(self, root):
              if not root:return 0
              else:return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))
    

##112. Path Sum(路径和)

  • 难度:Easy

  • 题意:
    给定二叉数组和数字 sum,检测是否有从根节点到叶子节点的路径使得路径上节点值的和为 sum

  • 思路:
    直接递归求解即可。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @param {integer} sum
          # @return {boolean}
          def hasPathSum(self, root, sum):
              if not root :return False
              sum -= root.val
              if sum==0 and not root.left and not root.right:return True
              if sum!=0 and not root.left and not root.right:return False
              if root.left and not root.right:return self.hasPathSum(root.left,sum)
              if root.right and not root.left:return self.hasPathSum(root.right,sum)
              if root.right and root.left:return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)
    

##113. Path Sum II(路径和)

  • 难度:Medium

  • 题意:
    给定二叉数组和数字 sum,检测是否有从根节点到叶子节点的路径使得路径上节点值的和为 sum,并返回所有满足要求的路径。

  • 思路:
    递归的同时把当前路径作为参数传入即可。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @param {integer} sum
          # @return {integer[][]}
          def pathSum(self, root, sum):
              self.result = []
              self.reduce(root,sum,[])
              return self.result
    
          def reduce(self,root,sum,nodes0):
              nodes = nodes0[::]
              if not root:return
              else:
                  nodes.append(root.val)
                  sum-=root.val
                  if sum==0 and not root.left and not root.right:
                      self.result.append(nodes)
                  elif sum!=0 and not root.left and not root.right:
                      return
                  elif root.left and not root.right:
                      self.reduce(root.left,sum,nodes)
                  elif root.right and not root.left:
                      self.reduce(root.right,sum,nodes)
                  elif root.right and root.left:
                      self.reduce(root.left,sum,nodes)
                      self.reduce(root.right,sum,nodes)
    

##124. Binary Tree Maximum Path Sum (路径和)

  • 难度:Hard

  • 题意:
    给定一个二叉树,返回最大路径和。这里的路径指:任意连线两点之间的路径。

  • 思路:
    对任意节点,经过该节点的最大路径为【以左子为根向下遍历的最大路径】+ 该节点 +【以右子为根向下遍历的最大路径】。因此可以用递归解决。用一个全局变量记录最大路径,递归求解当前节点为根向下遍历的最大路径。

  • 代码:

      class Solution(object):
          def maxPathSum(self, root):
              """
              :type root: TreeNode
              :rtype: int
              """
              if not root:return 0
              self.maxv = -(2**31)
              self.maxSum(root)
              return self.maxv
    
          def maxSum(self,root):
              if not root:return 0
              v,lmax,rmax=root.val,0,0
              if root.left:
                  lmax=self.maxSum(root.left)
                  if lmax>0:
                      v+=lmax
              if root.right:
                  rmax=self.maxSum(root.right)
                  if rmax>0:
                      v+=rmax
              self.maxv=max(self.maxv,v)
              return max(root.val,root.val+lmax,root.val+rmax)
    

##129. Sum Root to Leaf Numbers(路径和)

  • 难度:Medium

  • 题意:
    给定一个二叉树只包含数字 0-9,每个从根到叶子节点的路径表示一个数字(根表示最高位)。求所以从根到叶子节点数字之和。

  • 思路:
    使用递归的方法,传递父路径代表数字 n,则当前路径为 n*10+root。递归到叶子节点的时候把数字求和即可。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer}
          def sumNumbers(self, root):
              self.sum=0
              self.reduce(root,0)
              return self.sum
    
          def reduce(self,root,n):
              if not root:
                  self.sum+=n
              elif not root.left and not root.right:
                  n = 10*n+root.val
                  self.sum+=n
              else:
                  n = 10*n+root.val
                  if root.left:self.reduce(root.left,n)
                  if root.right:self.reduce(root.right,n)
    

##114. Flatten Binary Tree to Linked List (链表)

  • 难度:Medium

  • 题意:
    给定一棵二叉树,要求就定把树变为一个链表。

  • 思路:
    求当前节点的左子树的最右下角,并把当前节点右子树接到左子树最右下角,然后把左子树变为右子树。循环向右推进即可。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {void} Do not return anything, modify root in-place instead.
          def flatten(self, root):
              if not root:return
              while root:
                  if root.left:
                      node = root.left
                      while node.right:
                          node = node.right
                      node.right = root.right
                      root.right = root.left
                      root.left = None
                  root = root.right
    

##116. Populating Next Right Pointers in Each Node (按层次遍历)

  • 难度:Medium

  • 题意:
    给定一棵二叉树,对于每个节点如果存在相邻(同层右侧)节点,则填充 next 指针。假定给定的是一棵完全二叉树。

  • 思路:
    按层次遍历,使用 tag 标记当前层有多少个节点。

  • 代码:

      class Solution:
          # @param root, a tree link node
          # @return nothing
          def connect(self, root):
              nodeList = [root]
              tag = 1
              i = 1
              while len(nodeList):
                  treeNode = nodeList.pop(0)
                  if  treeNode and treeNode.left:
                      nodeList.extend([treeNode.left,treeNode.right])
                  if i == tag:
                      i = 1
                      tag *= 2
                  else:
                      if len(nodeList):
                          treeNode.next = nodeList[0]
                      i += 1
    

##117. Populating Next Right Pointers in Each Node II (按层次遍历)

  • 难度:Hard

  • 题意:
    给定一棵二叉树,对于每个节点如果存在相邻(同层右侧)节点,则填充 next 指针。给定的树不一定是完全二叉树。

  • 思路:
    根据当前层已经串联起来的 next,来生成下一层的 next。即根据 next 横向遍历,判断子节点情况,来串联下一层。横向遍历前需要记下,下一层的最左边的节点。

  • 代码:

      class Solution(object):
          def connect(self, root):
              """
              :type root: TreeLinkNode
              :rtype: nothing
              """
              if not root:return
              node=root
              ##自上而下遍历
              while node:
                  down = None
                  ##横向遍历
                  while node:
                      ##记录下一层最左边节点
                      if not down:
                          if node.left: down = node.left
                          elif node.right: down = node.right
                      nex = node.next
                      ##跳过无子节点的节点
                      while nex:
                          if nex.left or nex.right:
                              break
                          nex=nex.next
                      ##串联下一层
                      if node.left and node.right:
                          node.left.next = node.right
    
                      if node.left and not node.right and nex:
                          if nex.left:
                              node.left.next=nex.left
                          else:
                              node.left.next=nex.right
                      if node.right and nex:
                          if nex.left:
                              node.right.next=nex.left
                          else:
                              node.right.next=nex.right
                      node=nex
                  node=down
    

##173. Binary Search Tree Iterator (二叉搜索树)

  • 难度:Medium

  • 题意:
    实现二叉搜索树的迭代器。next 方法返回下一最小数字。hasNext 方法返回是否存在下一最小数字。

  • 思路:
    二叉搜索其实就是中序遍历。因此借助栈来实现,在初始化时,就将跟节点的所有左子入栈。调用 next 方法,返回栈顶,并将栈顶右子树的所有左子入栈。若栈为空,则无 next。

  • 代码:

      class BSTIterator:
          # @param root, a binary search tree's root node
          def __init__(self, root):
              self.stack=[]
              while root:
                  self.stack.append(root)
                  root=root.left
    
          # @return a boolean, whether we have a next smallest number
          def hasNext(self):
              return len(self.stack)!=0
    
          # @return an integer, the next smallest number
          def next(self):
              if self.stack:
                  root=self.stack.pop(-1)
                  rig = root.right
                  while rig:
                      self.stack.append(rig)
                      rig=rig.left
                  return root.val
              return None
    

##199. Binary Tree Right Side View (按层次遍历)

  • 难度:Medium

  • 题意:
    给定一个二叉树,想象你从右侧看这棵树,自上而下返回你能看到的数字。

  • 思路:
    直接按层次遍历便可。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer[]}
          def rightSideView(self, root):
              result=[]
              values = self.levelOrder(root)
              for row in values:
                  result.append(row[-1])
              return result
    
          def levelOrder(self, root):
              if not root :return []
              levels = [[root]]
              values = [[root.val]]
              for level in levels:
                  newLevel = []
                  newValue = []
                  for node in level:
                      if node.left:
                          newLevel.append(node.left)
                          newValue.append(node.left.val)
                      if node.right:
                          newLevel.append(node.right)
                          newValue.append(node.right.val)
                  if newLevel:
                      levels.append(newLevel)
                      values.append(newValue)
              return values
    

##222. Count Complete Tree Nodes (完全二叉树)

  • 难度:Medium

  • 题意:
    给定一个完全二叉树,返回节点个数。

  • 思路:
    对于完全二叉树,关键是找到最底层没有叶子的位置即可。若是满二叉树则可以直接算出节点个数。因此可以采用递归的方法查找节点缺失未知。若树最左深度=最右深度,则为满二叉树。否则递归求左子和右子数量。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {integer}
          def countNodes(self, root):
              return self.counter(root)
    
          def leftDeep(self, root):
              i = 0
              node = root
              if not node:
                  return 0
              while node.left:
                  i += 1
                  node = node.left
              return i
    
          def rightDeep(self, root):
              i = 0
              node = root
              if not node:
                  return 0
              while node.right:
                  i += 1
                  node = node.right
              return i
    
          def counter(self, root):
              if not root:
                  return 0
              else:
                  l = self.leftDeep(root)+1
                  r = self.rightDeep(root)+1
                  if l == r:
                      return 2 ** l - 1
                  else:
                      return self.counter(root.left) + self.counter(root.right) + 1
    

##226. Invert Binary Tree

  • 难度:Easy

  • 题意:
    左右翻转一棵二叉树。

  • 思路:
    传说中 90% 的谷歌工程师没办法在白板完成的题目。思路很简单,递归翻转左右子树。

  • 代码:

      class Solution:
          # @param {TreeNode} root
          # @return {TreeNode}
          def invertTree(self, root):
              if not root:return root
              root.left,root.right=root.right,root.left
              self.invertTree(root.left)
              self.invertTree(root.right)
              return root
    

##230. Kth Smallest Element in a BST (二叉搜索树)

  • 难度:Medium

  • 题意:
    给定一个二叉搜索树,返回其第 k 小的元素。

  • 思路:
    借助栈实现二叉搜索树的遍历,弹出第 k 个为答案。

  • 代码:

      class Solution(object):
          def kthSmallest(self, root, k):
              """
              :type root: TreeNode
              :type k: int
              :rtype: int
              """
              stack=[]
              node = root
              while node:
                  stack.append(node)
                  node = node.left
              x=1
              while stack and x<=k:
                  node = stack.pop()
                  x+=1
                  right = node.right
                  while right:
                      stack.append(right)
                      right=right.left
              return node.val
    

##235. Lowest Common Ancestor of a Binary Search Tree (共同祖先)

  • 难度:Easy

  • 题意:
    给定一个二叉搜索树,找到给定两个节点的最近公共祖先。

  • 思路:
    使用递归的方法,若当前节点等于其中一个节点,则该节点必为公共节点。若两个数分布在该节点两侧,则该节点比为公共节点。若均在左侧,递归左子。若均在右侧,递归右子。

  • 代码:

      class Solution(object):
          def lowestCommonAncestor(self, root, p, q):
              """
              :type root: TreeNode
              :type p: TreeNode
              :type q: TreeNode
              :rtype: TreeNode
              """
    
              if root==p or root ==q:return root
              elif root.val > max(p.val,q.val):
                  return self.lowestCommonAncestor(root.left,p,q)
              elif root.val < min(p.val,q.val):
                  return self.lowestCommonAncestor(root.right,p,q)
              else:
                  return root
    

##236. Lowest Common Ancestor of a Binary Tree (共同祖先)

  • 难度:Medium

  • 题意:
    给定一个二叉树,找到给定两个节点的最近公共祖先。

  • 思路:
    该题和 235 的区别在于,不是二叉搜索树。因此无法通过数字的大小关系,判断数字在哪个子树中。但是整体思路还是不便。我们观察发现,其实在递归左子或右子的时候,其实同时也在查找两个给定的树。因此也可以判断两个数字在当前节点的哪一侧。而且更巧的是,若在同一侧,递归先找到的那个节点就是共同祖先。

  • 代码:

      class Solution(object):
          def lowestCommonAncestor(self, root, p, q):
              """
              :type root: TreeNode
              :type p: TreeNode
              :type q: TreeNode
              :rtype: TreeNode
              """
              if not root: return None
              if 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
    

##257. Binary Tree Paths (路径)

  • 难度:Easy

  • 题意:
    给定一个二叉树,返回所有从根到叶子节点的路径。

  • 思路:
    递归进行 dfs,同时记录路径即可。

  • 代码:

      class Solution(object):
          def binaryTreePaths(self, root):
              """
              :type root: TreeNode
              :rtype: List[str]
              """
              self.result=[]
              self.dfs(root,[])
              return self.result
    
          def dfs(self,root,path0):
              path = path0[::]
              if not root :return
              path.append(str(root.val))
              if not root.left and not root.right:
                  self.result.append('->'.join(path))
              else:
                  if root.left:
                      self.dfs(root.left,path)
                  if root.right:
                      self.dfs(root.right,path)
    

##297. Serialize and Deserialize Binary Tree

  • 难度:Hard

  • 题意:
    要求设计二叉树的序列化和反序列化函数,要求序列化返回一个字符串。反序列化根据这个字符串能重新构造出这颗树

  • 思路:
    其实 leetcode 中对树的表示就是一种很好的序列化。因此序列化只需要借助队列,按层次遍历,若无子节点则用“#”代替。若该树为完全二叉树,则对第 i 个节点,其左右节点分别为 2i+1 和 2i+2。但是若为非完全二叉树,则对于之前出现的每个#,由于#没有左右子节点,会使当前节点的子节点提前 2*(当前节点之前#个数)

  • 代码:

      class Codec:
    
          def serialize(self, root):
              """Encodes a tree to a single string.
    
              :type root: TreeNode
              :rtype: str
              """
              if not root:return None
              q =[root]
              i,endIndex=0,1
              while i<endIndex:
                  if q[i]:
                      q.append(q[i].left)
                      q.append(q[i].right)
                      endIndex+=2;
                  i+=1
              res=[]
              for node in q:
                  if node:
                      res.append(str(node.val))
                  else:
                      res.append("#")
              return ','.join(res)
    
    
    
    
          def deserialize(self, data):
              """Decodes your encoded data to tree.
    
              :type data: str
              :rtype: TreeNode
              """
              if not data:return None
              values = data.split(',')
              nodes = [None]*len(values)
              count=0
              for i in range(len(values)):
                  if values[i] != '#':
                      nodes[i] = TreeNode(int(values[i]))
              for i in range(len(nodes)):
                  if not nodes[i]:
                      count+=1
                  else:
                      nodes[i].left=nodes[2*(i-count)+1]
                      nodes[i].right=nodes[2*(i-count)+2]
              return nodes[0]
    

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖 • 1 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • zonghua

    谢谢博主,这么多东西感觉我都可以记住了

  • xcatliu

    这是所有的树的题目吗?

  • zonghua

    @xcatliu 图的是不是高阶的了?

  • manyue

    不明觉厉~

推荐标签 标签

  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    167 引用 • 1509 回帖
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 257 关注
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    124 引用 • 580 回帖
  • GraphQL

    GraphQL 是一个用于 API 的查询语言,是一个使用基于类型系统来执行查询的服务端运行时(类型系统由你的数据定义)。GraphQL 并没有和任何特定数据库或者存储引擎绑定,而是依靠你现有的代码和数据支撑。

    4 引用 • 3 回帖 • 6 关注
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 561 关注
  • 心情

    心是产生任何想法的源泉,心本体会陷入到对自己本体不能理解的状态中,因为心能产生任何想法,不能分出对错,不能分出自己。

    59 引用 • 369 回帖 • 1 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖 • 3 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 652 关注
  • V2Ray
    1 引用 • 15 回帖 • 1 关注
  • Mobi.css

    Mobi.css is a lightweight, flexible CSS framework that focus on mobile.

    1 引用 • 6 回帖 • 733 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 615 关注
  • Sphinx

    Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。

    1 引用 • 209 关注
  • 30Seconds

    📙 前端知识精选集,包含 HTML、CSS、JavaScript、React、Node、安全等方面,每天仅需 30 秒。

    • 精选常见面试题,帮助您准备下一次面试
    • 精选常见交互,帮助您拥有简洁酷炫的站点
    • 精选有用的 React 片段,帮助你获取最佳实践
    • 精选常见代码集,帮助您提高打码效率
    • 整理前端界的最新资讯,邀您一同探索新世界
    488 引用 • 383 回帖 • 6 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    21 引用 • 245 回帖 • 248 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    264 引用 • 665 回帖 • 1 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 2 关注
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 2 关注
  • 音乐

    你听到信仰的声音了么?

    60 引用 • 511 回帖
  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 127 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 705 关注
  • OnlyOffice
    4 引用 • 2 关注
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1347 回帖
  • 百度

    百度(Nasdaq:BIDU)是全球最大的中文搜索引擎、最大的中文网站。2000 年 1 月由李彦宏创立于北京中关村,致力于向人们提供“简单,可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”,象征着百度对中文信息检索技术的执著追求。

    63 引用 • 785 回帖 • 181 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    6 引用 • 14 回帖