leetcode解题报告-树

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

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

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

对应的树的遍历方法有 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 回帖

相关帖子

欢迎来到这里!

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

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

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

  • xcatliu

    这是所有的树的题目吗?

  • zonghua

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

  • manyue

    不明觉厉~

推荐标签 标签

  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    944 引用 • 1459 回帖 • 17 关注
  • JRebel

    JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。

    26 引用 • 78 回帖 • 664 关注
  • SendCloud

    SendCloud 由搜狐武汉研发中心孵化的项目,是致力于为开发者提供高质量的触发邮件服务的云端邮件发送平台,为开发者提供便利的 API 接口来调用服务,让邮件准确迅速到达用户收件箱并获得强大的追踪数据。

    2 引用 • 8 回帖 • 483 关注
  • 代码片段

    代码片段分为 CSS 与 JS 两种代码,添加在 [设置 - 外观 - 代码片段] 中,这些代码会在思源笔记加载时自动执行,用于改善笔记的样式或功能。

    用户在该标签下分享代码片段时需在帖子标题前添加 [css] [js] 用于区分代码片段类型。

    69 引用 • 372 回帖
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 1 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现,服务器端用 Erlang 语言编写,支持多种语言客户端,如:Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 362 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    6 引用 • 63 回帖
  • Elasticsearch

    Elasticsearch 是一个基于 Lucene 的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于 RESTful 接口。Elasticsearch 是用 Java 开发的,并作为 Apache 许可条款下的开放源码发布,是当前流行的企业级搜索引擎。设计用于云计算中,能够达到实时搜索,稳定,可靠,快速,安装使用方便。

    117 引用 • 99 回帖 • 212 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    190 引用 • 1057 回帖
  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    186 引用 • 318 回帖 • 302 关注
  • 百度

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

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

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

    6 引用 • 14 回帖 • 2 关注
  • NGINX

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

    311 引用 • 546 回帖
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    8112 引用 • 37001 回帖 • 160 关注
  • SEO

    发布对别人有帮助的原创内容是最好的 SEO 方式。

    35 引用 • 200 回帖 • 22 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 680 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 587 关注
  • danl
    132 关注
  • Gitea

    Gitea 是一个开源社区驱动的轻量级代码托管解决方案,后端采用 Go 编写,采用 MIT 许可证。

    4 引用 • 16 回帖 • 5 关注
  • 服务器

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

    125 引用 • 588 回帖
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 742 关注
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 19 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • 倾城之链
    23 引用 • 66 回帖 • 136 关注