树是最常考察的数据结构。由于树的定义是递归的(树的子树也是树),因此大部分的树的问题,如求树的最大深度、判定树是否平衡、共同祖先等,可以由递归进行求解,这也是最简单最直接的方式。
但是,通常面试官都希望你答出非递归解法。如前中后序的非递归解法都是借助栈进行实现(利用栈先进后出的特性,结合进出栈的时机)。先序列遍历和中序遍历对栈的操作相同,栈顶左子一直进栈直到最左下,弹栈,右子进栈。然后循环操作即可。唯一不同是先序遍历是在进栈前访问,中序遍历是在弹栈的时候访问。后序遍历,进栈的顺序为根右左,由于栈的特性会使出栈时为左右根。进栈时需标记当前节点左右子是否已经进栈了。树的按层次遍历是借助队列先进先出的特性实现的。
对应的树的遍历方法有 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:
面试官肯定会问,还有非递归的解法吗?这里非递归的解法也非常简单,就是深度优先遍历(先序遍历)。深度优先遍历的非递归解法是借助栈来实现的,- 跟节点入栈
- 循环将栈顶的左子入栈,直到无左子
- 弹出栈顶,将其右子入栈
- 循环 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]
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于