面试高频算法题之二叉树
二叉树
全文概览
基础知识
树是一种非常重要的非线性数据结构，而二叉树是一种特殊的树。
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
二叉树的分类
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树被称为满二叉树。
完全二叉树
完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
二叉查找树
二叉查找树又被称为是二叉搜索树，它是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
左、右子树也分别为二叉查找树；
平衡二叉树
平衡二叉树（Balanced Binary Tree）又被称为AVL树，它是一棵特殊的二叉查找树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
它很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
二叉树的存储方式
二叉树的存储方式分为两种，分别为链式存储和顺序存储。
链式存储
二叉树的链式存储是用链表来实现的，对于链表中的每个结点，它不仅包含了数据域，还包含了两个指针域，分别指向其左、右孩子结点，如下图所示。
顺序存储
二叉树的顺序存储是用数组来实现的，它用一组连续的存储单元来存储二叉树中的数据元素。为了能反映出结点之间的逻辑关系。可以采用编号的方法，即对二叉树按完全二叉树进行编号，其中编号为 i 的结点存储在数组中下标为 i 的分量中。
我们可以很容易知道，对于下标为 i 的父节点，其左、右孩子的下标分别为 2 * i + 1 和 2 * i + 2。
二叉树的遍历
二叉树的遍历主要有两种遍历方式，即深度优先遍历和广度优先遍历。
深度优先遍历（Depth First Search，简称DFS）
二叉树的深度优先遍历是指从根节点出发，然后对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。它可以细分为前序遍历、中序遍历和后续遍历。
前序遍历
先访问根节点，然后遍历其左子树，最后遍历其右子树
中序遍历
先遍历其左子树，然后访问根节点，最后遍历其右子树。
后续遍历
先遍历其左子树，然后遍历其右子树，最后访问根节点。
广度优先遍历（Breath First Search，简称BFS）
广度优先遍历是指从根节点出发，按层一层层的去遍历二叉树的节点。
广度优先遍历也叫做层序遍历。
实现二叉树的先序、中序和后序遍历
问题描述
给定一个二叉树，分别按照二叉树的先序、中序和后序打印所有节点。
要求：空间复杂度是O(n)，时间复杂度是O(n)。
示例：
输入: [1,null,2,3]
1
\
2
/
3
输出: [[1,2,3],[1,3,2],[3,2,1]]分析问题
拿到这个问题时，首先我们需要知道什么是先序遍历、中序遍历和后序遍历。
先序遍历：按照根节点 -> 左子树 -> 右子树的顺序来遍历这颗树，而访问左、右子树时，也采用同样的顺序进行遍历，直到遍历完整棵树。
中序遍历：按照左子树 -> 根节点 -> 右子树的顺序来遍历这棵树，而访问左、右子树时，也采取同样的顺序进行遍历，直到遍历完整颗树。
后续遍历：按照左子树 -> 右子树 -> 根结点的顺序来遍历这棵树，而访问左、右子树时，也采取同样的顺序进行遍历，直到遍历完整颗树。
根据二叉树的先序、中序、后序的定义，我们可以很直观的想到采用递归的方式来遍历整棵树。下面我们来看一下如何使用递归的方式实现二叉树的先序、中序和后序遍历。
递归
使用递归来遍历，当遇到根节点的左子树或右子树不为空时，我们就把它的左子树或右子树再当做一颗完整的树来处理。
为了方便理解，我们先看一下结点的定义。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right先序遍历
def preorder(self,root):
if not root:
return
self.res.append(root.val)
self.preorder(root.left)
self.preorder(root.right)中序遍历
def inorder(self,root):
if not root:
return
self.inorder(root.left)
self.res.append(root.val)
self.inorder(root.right)后续遍历
def postorder(self, root):
if not root:
return
self.postorder(root.left)
self.postorder(root.right)
self.res.append(root.val)代码的完整实现
class Solution:
res=[]
def threeOrders(self, root):
result = []
self.preorder(root)
result.append(self.res[:])
self.res.clear()
self.inorder(root)
result.append(self.res[:])
self.res.clear()
self.postorder(root)
result.append(self.res[:])
self.res.clear()
return result
def postorder(self, root):
if not root:
return
self.postorder(root.left)
self.postorder(root.right)
self.res.append(root.val)
def preorder(self,root):
if not root:
return
self.res.append(root.val)
self.preorder(root.left)
self.preorder(root.right)
def inorder(self,root):
if not root:
return
self.inorder(root.left)
self.res.append(root.val)
self.inorder(root.right)非递归
同时我们也可以采用非递归的方式来实现，在实现的过程中我们需要引入一个新的数据结构栈。我们以中序遍历为例来看一下执行过程。
下面我们来看一下代码如何实现。
from pyarabic.stack import Stack
def inorder(root):
res=[]
stack=Stack()
while root or stack:
while root:
stack.push(root)
root=root.left
root=stack.pop()
res.append(root.val)
root=root.right
return res同理，先序遍历和后序遍历也可以使用非递归的方式实现。
下面，我们给出采用非递归的方式来实现二叉树的三种遍历的代码。
class Solution:
def threeOrders(self, root):
result = []
result.append(self.preorder(root))
result.append(self.inorder(root))
result.append(self.postorder(root))
return result
def postorder(self, root):
res = []
if not root:
return res
stack = []
prev = None
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if not root.right or root.right == prev:
##root.right == prev 用来判断右孩子是否已经访问过了
res.append(root.val)
prev = root
root = None
else:
stack.append(root)
root = root.right
return res
def preorder(self, root):
res = []
if not root:
return res
stack = []
while stack or root:
while root:
res.append(root.val)
stack.append(root)
root=root.left
root = stack.pop()
root = root.right
return res
def inorder(self, root):
res = []
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
return res二叉树的层序遍历
问题描述：
102. 二叉树的层序遍历
给你一颗二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7返回其层序遍历结果：[ [3],[9,20],[15,7]]
分析问题
在开始之前，我们这里先来回顾一下什么是BFS（广度优先搜索）和DFS（深度优先搜索）。
- BFS：广度优先搜索是从图中一个未访问的顶点 V 开始，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点，一层层的搜索下去。
- DFS：深度优先搜索是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
下面我们来看一下通过BFS和DFS来对二叉树进行遍历。
其代码实现如下所示。
DFS遍历：
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)BFS遍历：
def bfs(root):
res = []
if root:
queue = [root]
while queue:
node=queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res回过头来，我们来看一下题目，题目要求是按照层序遍历二叉树。那什么是层序遍历呢，简单来说，就是将二叉树分层，然后对每一层按照从左到右的顺序进行遍历。
看到这里，你有没有发现它和BFS的遍历顺序是一样的。我们可以直接使用BFS算法得出层序遍历的结果。这里需要注意一下，层序遍历和BFS遍历输出的结果是有点区别的。层序遍历要求我们需要区分每一层，即输出一个二维数组。而BFS遍历输出的结果是一维数组，是没办法区分是哪一层的，所以，我们需要对BFS代码稍微修改一下。
def bfs(root):
if not root:
return []
res = []
queue = []
queue.append(root)
while queue:
#该层的节点数量
size = len(queue)
tmp = []
#遍历把该层元素全部输出
while size:
node = queue.pop(0)
tmp.append(node.val)
size = size - 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return res复杂度分析。
- 时间复杂度：二叉树中每个结点进队和出队各一次，所以时间复杂度为O(n)。
- 空间复杂度：队列中的元素不会超过n个，所以空间复杂度是O(n)。
按之字型顺序打印二叉树
LeetCode 剑指 Offer 32 - III. 从上到下打印二叉树 III
问题描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）。
要求：空间复杂度是O(n)，时间复杂度是O(n)。
例如：给定的二叉树是 {1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是[[1]，[3,2]，[4,5]]。
如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。
分析问题
根据题目要求，我们可以得出。
- 二叉树是从上到下按层进行输出的。
- 奇数层是按照从左到右打印，偶数层是按照从右到左打印
因为题目要求是按层进行遍历，所以我们可以知道是采用层序遍历的算法，不过这里和层序遍历有一点不同的是，对应偶数层，我们要逆序输出，即从右到左打印，所以我们需要引入一个双端队列数据结构，利用它两端都可以添加元素的特性，对奇数层和偶数层进行不同的处理。
- 奇数层：添加到队列的尾部
- 偶数层：添加到队列的头部
对于元素 [1，2，3]，如果从尾部添加，则遍历完成时，队列中元素的顺序是 [1, 2, 3] ，输出后是正序的。如果从头部添加，则遍历完成时，队列中元素的顺序是 [3, 2, 1]，输出后是逆序的，从而解决问题。最后，我们来看一下代码的实现。
import collections
def levelOrder(root):
#如果根节点为空，直接返回空值
if not root:
return []
res = []
deque = collections.deque([root])
#队列不为空时
while deque:
#双端队列，保存遍历的元素
tmp = collections.deque()
#遍历该层元素
for _ in range(len(deque)):
node = deque.popleft()
#偶数层，从前边插入，即队头
if len(res) % 2:
tmp.appendleft(node.val)
else:
#奇数层，从后边插入，即队尾
tmp.append(node.val)
#node的左右孩子入队
if node.left:
deque.append(node.left)
if node.right:
deque.append(node.right)
#添加到结果列表中
res.append(list(tmp))
return res该算法的时间复杂度和空间复杂度都是O(N)。
其实我们也可以不使用双端队列，我们可以直接使用列表来实现。如果是奇数层，我们直接添加到结果中，如果是偶数层，我们把列表逆置，然后再加入结果。
def levelOrder(root):
if not root:
return []
res = []
queue = collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if len(res) % 2==0:
#偶数层,逆序添加
res.append(tmp[::-1])
else:
#奇数层
res.append(tmp)
return res该算法的时间复杂度和空间复杂度都是O(N)。
重建二叉树
问题描述
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例：
输入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]
分析问题
由于先序遍历是先遍历根节点，然后递归遍历左子树、右子树，而中序遍历是先递归遍历左子树，然后遍历根节点，最后递归遍历右子树。
我们可以知道先序遍历的第一个元素是树的根节点root。由于先序遍历和中序遍历的结果中都不含重复的数字，所以我们可以查找root在中序遍历中的索引，然后将中序遍历结果划分为[左子树 | 根节点 | 右子树]，然后我们根据中序遍历中左子树和右子树的节点数量，将先序遍历结果划分为[根节点 | 左子树 | 右子树]。这样，我们就可以确定出根结点、左子树根节点、右子树根节点的位置，然后我们再递归的进行求解。
下面我们来看一下代码实现。
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, vin):
# write code here
dic={}
#为了提升查找效率，将中序遍历里的值和索引放入字典中
for i in range(len(vin)):
dic[vin[i]] = i
#开始时，根节点在先序遍历的索引为0，子树的左边界为0，右边界为len(inorder) - 1
return self.recur(0, 0, len(vin) - 1,pre,dic)
"""
root:根节点在先序遍历中的索引位置
left:子树在中序遍历中的左边界
right:子树在中序遍历中的右边界
"""
def recur(self,root, left, right,preorder,dic):
if left > right:
return # 递归终止
node = TreeNode(preorder[root]) # 建立根节点
#找出根节点在中序遍历的索引位置，将先序遍历划分为[根节点|左子树|右子树]
i = dic[preorder[root]]
#递归遍历左子树，左子树的根节点在root的下一个位置，即root+1
node.left = self.recur(root + 1, left, i - 1,preorder, dic)
#递归遍历右子树，左子树的长度为i-left,
#所以右子树的根节点在先序遍历的位置为i-left+root+1
node.right = self.recur(i - left + root + 1, i + 1, right, preorder,dic)
return node # 回溯返回根节点二叉树的右视图
问题描述
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例：
输入：[1,2,3,null,5,null,4]
输出：[1,3,4]
分析问题
广度优先搜索
我们从右边观察一个二叉树，我们能看到的节点是二叉树每一层上的最右边的节点。所以我们可以对二叉树进行层次遍历，对于二叉树的每层来说，最右边的节点一定是最后遍历到的。
二叉树的层次遍历是采用广度优先搜索实现的。在执行广度优先搜索时，我们对每一层都从左到右访问。因此，只保留每一层最后访问的节点，我们就可以在遍历完整棵树后得到每层的最右的结点。
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
#key 为层数 value为节点值
rightNode = dict()
#代表二叉树的深度
max_depth = -1
queue = [(root, 0)]
while queue:
node, depth = queue.pop(0)
#记录二叉树的最大深度
max_depth = max(max_depth, depth)
#由于每一层中，最后访问的节点是最右边的节点，
#所以我们进行不断的更新就好
rightNode[depth] = node.val
if node.left:
#放入左节点
queue.append((node.left, depth + 1))
if node.right:
#放入右节点
queue.append((node.right, depth + 1))
return [rightNode[depth] for depth in range(max_depth + 1)]
算法的时间复杂度是O(n)。每个元素进出队列一次，所以时间复杂度是O(n)。
算法的空间复杂度是O(n)。每个元素进队列一次，所以队列的长度不会超过n，所以空间复杂度是O(n)。
深度优先搜索
其实我们也可以使用深度优先搜索来求解。在搜索的过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。所以，在访问到树的每一层时，我们存储该层的第一个节点，等遍历完整棵树后，就可以得到最终的结果数组。
class Solution:
def rightSideView(self, root):
if not root:
return []
#key 为层数 value为节点值
rightNode = dict()
#代表二叉树的深度
max_depth = -1
stack = [(root, 0)]
while stack:
node, depth = stack.pop()
#记录二叉树的最大深度
max_depth = max(max_depth, depth)
#如果不存在，才加入
#只保存没一层第一个结点
if not rightNode.__contains__(depth):
rightNode[depth]=node.val
#栈先入后出，所以先出栈右节点
if node.left:
#放入左节点
stack.append((node.left, depth + 1))
if node.right:
#放入右节点
stack.append((node.right, depth + 1))
return [rightNode[depth] for depth in range(max_depth + 1)]该算法的时间复杂度和空间复杂度都是O(n)。
二叉树的最大深度
问题描述
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
示例：
输入：给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7输出：3
解释：二叉树的最大深度是 3
分析问题
对二叉树进行遍历，一般有两种方式，即深度优先搜索（DFS）和广度优先搜索（BFS）。所以求解这个问题，我们也可以有两种方式。
深度优先搜索
二叉树的最大深度等于根节点的左子树的深度和右子树的深度的最大值+1，即 max(maxDepth(root.left), maxDepth(root.right))+1。所以，我们可以采用递归的方式来求解。
下面我们来看一下代码实现。
class Solution:
def maxDepth(self, root):
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1该算法的时间复杂度和空间复杂度都是O(N)。
广度优先搜索
我们也可以通过广度优先搜索来实现，每遍历树的一层的时候，我们就使计数器 +1，等遍历结束后，就得到了树的最大深度。
class Solution:
def maxDepth(self, root):
if not root:
return 0
queue = []
#根节点入队
queue.append(root)
res=0
while queue:
#队列长度
m=len(queue)
#遍历该层元素
for i in range(m):
node=queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
#遍历完一层，计算器+1
res = res + 1
return res该算法的时间复杂度和空间复杂度都是O(N)。
判断是否是平衡二叉树
问题描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
平衡二叉树（Balanced Binary Tree）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
示例：
输入：给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7输出：true
分析问题
平衡二叉树是指二叉树的每个节点的左右子树的高度差的绝对值不超过1。根据定义，一颗二叉树是平衡二叉树，当且仅当它的所有子树也是平衡二叉树，所以，我们可以使用递归的方式来求解，我们根据递归的顺序不同，可以分为自顶向下和自底向上两种方式。
自顶向下方式（先序遍历+判断）
首先我们定义一个函数height，用来计算二叉树中任意一个节点的高度。然后通过先序遍历二叉树，对于当前遍历到的节点，我们首先计算其左子树和右子树的高度，然后判断其左右子树的高度差是否小于1，如果小于1，代表以该节点为根节点的二叉树是平衡二叉树，然后再分别递归地遍历左右节点，并判断左子树和右子树是否平衡。这是一个自顶向下的过程。如果所有子树都平衡，代表该树是一颗平衡二叉树。
我们来看一下代码实现。
class Solution:
def IsBalanced_Solution(self, pRoot):
#求二叉树的高度
def height(root):
if not root:
return 0
return max(height(root.left), height(root.right)) + 1
#如果数为空，代表是平衡二叉树，直接返回
if not pRoot:
return True
#左子树的高度
leftheight=height(pRoot.left)
#右子树的高度
rightheight=height(pRoot.right)
#代表以该节点为根节点的二叉树是平衡的
if abs(leftheight-rightheight) <=1:
#再递归判断其左右子树是否是平衡的
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
return False自底向上的递归
在上面的算法中，我们可以发现对于同一个节点，函数height会被重复调用，导致执行效率不高，如果采用自底向上的解法，对于每个节点，函数height只会被调用一次。
自底向上的递归是指，我们对二叉树进行后序遍历，对于当前遍历到的节点，我们先递归的去判断其左、右子树是否是平衡的，然后再判断以当前节点为根的二叉树是否是平衡的。如果一棵子树是平衡的，则返回其高度，否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定是不平衡。
下面我们来看一下代码实现。
class Solution:
def IsBalanced_Solution(self, pRoot):
#递归的求树的高度
def height(root):
if not root:
return 0
#左子树的高度
left_height= height(root.left)
#右子树的高度
right_height = height(root.right)
#子树的高度为-1，代表子树不是平衡二叉树，那么该树也不是平衡二叉树，返回-1
#abs(leftHeight - rightHeight) > 1 代表左右子树的高度差大于1，表示该树是不平衡的，返回-1
if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
return -1
else:
#否则，返回树的高度
return max(left_height, right_height) + 1
#如果树的高度不是-1，代表该树是平衡二叉树
return height(pRoot) >= 0该算法的时间复杂度是O(N)，空间复杂度也是O(N)。
二叉树根节点到叶子节点的所有路径和
LeetCode 剑指 Offer II 049. 从根节点到叶节点的路径数字之和
问题描述
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。计算从根节点到叶节点生成的所有数字之和。
示例：
输入：root = [1,2,3]
输出：25
解释：从根到叶子节点路径 1->2 代表数字 12，从根到叶子节点路径 1->3 代表数字13，因此，数字总和 = 12 + 13 = 25。
分析问题
根据题意，我们可以知道每个节点对应一个数字，其值等于其父节点对应的数字乘以10再加上该节点的值。只要计算出所有叶子节点对应的数字，然后对其求和，即可得到结果。
遍历求出所有叶子节点对应的数字，我们可以采用深度优先搜索和广度优先搜索来实现。
深度优先搜索
从根节点开始遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到结果中。如果遇到的是非叶子节点，则计算该节点的值，然后对其子节点进行递归遍历。
class Solution:
def sumNumbers(self, root):
def dfs(root, pre):
#如果为空，返回0
if not root:
return 0
total = pre * 10 + root.val
#如果遇到叶子节点，加到结果中，否则递归求解其子节点
if not root.left and not root.right:
return total
else:
return dfs(root.left, total) + dfs(root.right, total)
#从根节点开始递归
return dfs(root, 0)该算法的时间复杂度和空间复杂度都是O(n)。
广度优先搜索
使用广度优先搜索来求解此题时，我们需要维护两个队列来分别存储节点和节点对应的数字。开始时我们将根节点和根节点对应的值分别加入两个队列中。如果队列不为空，我们就从两个队列分别取出一个节点和一个数字，进行如下操作：
- 如果当前节点是叶子节点，我们就将该节点对应的数字加入到结果中。
- 如果当前节点不是叶子节点，则将当前节点的非空子节点入队，同时根据当前节点对应的数字和其子节点对应的数字计算出子节点代表的数字，并入队。
搜索结束后，就可以得到所有叶节点对应的数字之和。
下面我们来看一下代码实现。
import collections
class Solution:
def sumNumbers(self, root):
#树为空，直接返回0
if not root:
return 0
total = 0
#根节点和对应的值都入队
nodeQueue = collections.deque([root])
numQueue = collections.deque([root.val])
#如果队列不为空
while nodeQueue:
#出队
node = nodeQueue.popleft()
num = numQueue.popleft()
left, right = node.left, node.right
#如果是叶子节点，加入结果中
if not left and not right:
total += num
else:
#否则，计算其叶子节点和其对应的数字，并同时入队
if left:
nodeQueue.append(left)
numQueue.append(num * 10 + left.val)
if right:
nodeQueue.append(right)
numQueue.append(num * 10 + right.val)
return total该算法的时间复杂度和空间复杂度都是O(n)。
二叉树根节点到叶子节点和为指定值的路径
LeetCode 剑指 Offer 34. 二叉树中和为某一值的路径
问题描述
给定一个节点数为 n 的二叉树和一个值 sum ，请找出所有的根节点到叶子节点的节点值之和等于给定值sum 的路径，如果没有则返回空。
例如：
给出如下的二叉树，sum = 22。
返回：[ [5,4,11,2], [5,8,9] ]
分析问题
这道题比较简单，本质上就是搜索二叉树。对于二叉树的搜索，我们知道有深度优先搜索和广度优先搜索两种，所有这道题我们也可以有两种方式来求解。
深度优先搜索
找出所有的根节点到叶子节点的节点值之和等于sum的路径，我们可以枚举每一条根节点到叶子节点的路径，如果路径和恰好为目标和时，我们就找到了一条满足条件的路径。
class Solution:
def pathSum(self, root, target):
if not root:
return []
#存放所有的路径
ret = list()
#记录根节点到当前节点的路径和，防止重复计算
path = list()
def dfs(root, target):
#将该节点对于的value加入path中
path.append(root.val)
target -= root.val
#如果为叶子节点，并且路径和等于target，则把该路径加入res中
if not root.left and not root.right and target == 0:
ret.append(path[:])
#如果左孩子不为空，继续去搜索
if root.left:
dfs(root.left, target)
#如果右孩子不为空，继续去搜索
if root.right:
dfs(root.right, target)
#将该节点弹出
path.pop()
dfs(root, target)
return ret广度优先搜索
我们也可以采用广度优先搜索的方式来求解。这里，我们使用一个哈希表来记录树中的每一个节点的父节点。在每一次找到一个满足条件的叶子节点时，我们就从该叶子节点出发，不断的向父节点迭代，即可还原出一条路径，使得从根节点到叶子节点的路径和等于目标值。
import collections
class Solution:
def pathSum(self, root, target):
#如果root为空，直接返回
if not root:
return []
ret = []
#用来保存父节点和子节点的关系
parent = {}
#根节点的父节点为None
parent[root]=None
#从该节点出发，一直寻找到根节点，还原出一条路径
def getPath(node):
tmp = []
while node:
tmp.append(node.val)
node = parent[node]
ret.append(tmp[::-1])
#建立一个队列，保存遍历到哪个节点，初始时，把根节点加入
node_que = collections.deque([root])
#记录从根节点走到某个节点时，累加的距离为多少，初始时为0
value_count_que = collections.deque([0])
while node_que:
#出队
node = node_que.popleft()
#将该节点的值进行累加
rec = value_count_que.popleft() + node.val
#如果是根节点，判断是否等于目标值，如果相等，则保存路径
if not node.left and not node.right:
if rec == target:
getPath(node)
else:
#如果左孩子存在，将节点加入node_que，将rec加入value_count_que
if node.left:
parent[node.left] = node
node_que.append(node.left)
value_count_que.append(rec)
#如果右孩子存在，将节点加入node_que，将rec加入value_count_que
if node.right:
parent[node.right] = node
node_que.append(node.right)
value_count_que.append(rec)
return ret判断一棵二叉树是否为搜索二叉树
问题描述
给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树。
输出描述：输出是否为搜索二叉树。
注意：空子树我们认为是符合搜索二叉树。
示例：
输入：{2,1,3}
输出：true
分析问题
首先，我们先来看一下搜索二叉树的定义。搜索二叉树满足如下条件：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
我们都知道中序遍历二叉树是先遍历左子树，然后遍历根节点，最后遍历右子树。而二叉搜索树保证了左子树的节点值均小于根节点的值，根节点的值均小于右子树的值。所以，当我们对二叉搜索树进行中序遍历时，得到的序列一定是升序的。这启示我们可以这么做，在中序遍历的过程中，检查当前节点的值是否大于中序遍历的前一个节点的值，如果均大于，说明中序遍历得到的序列是升序的，也就表明该树是二叉搜索树，否则不是。
class Solution:
def isValidBST(self, root) :
stack = []
#中序遍历的前一个节点的值
pre_data = float('-inf')
while stack or root:
#一直遍历到最左边的孩子
while root:
stack.append(root)
root = root.left
#栈中弹出一个元素
root = stack.pop()
#节点的值小于等于中序遍历的前一个pre_data，
#说明不是二叉搜索树，直接返回false
if root.val <= pre_data:
return False
pre_data = root.val
#遍历右子树
root = root.right
return True判断一棵二叉树是否为完全二叉树
问题描述
给定一棵二叉树，请判断该二叉树是否为完全二叉树。
输出描述：输出是否为完全二叉树。
注意：空子树我们认为是符合完全二叉树。
示例：
输入：{2,1,3}
输出：true
分析问题
在引出完全二叉树的定义之前，我们先来看一下什么是满二叉树。满二叉树是指除了最后一层叶子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是由满二叉树引出来的。对于深度为K的，有n个节点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，我们称之为完全二叉树。如下图所示。
根据完全二叉树的定义，我们可以通过广度优先搜索进行求解，每遇到一个节点时，我们进行判断。
- 如果节点的左孩子为空且右孩子不为空的时，该树不是完全二叉树。
- 如果第一次发现左、右两个孩子不是双全的时候，我们记录一下。如果后面访问到的节点出现非叶子节点时，那么表明该树不是完全二叉树。
def isAllTreeBST(self, root):
#如果是空树，直接返回True，因为空树也是完全二叉树
if not root:
return True
queue=collections.deque([root])
#遇到第一个非双全的节点，打个标记
flag=False
while queue:
node = queue.popleft()
left = node.left
right = node.right
#如果flag为true 且 访问到的节点出现非叶子节点时，表明是非完全树，返回False
if flag and not (left==None and right==None):
return False
#左孩子为空且右孩子不为空的时,表明是非完全树，返回False
if left==None and right != None:
return False
if left!=None:
queue.append(left)
if right!=None:
queue.append(right)
#遇到非全节点，设置flag=True
if left==None or right==None:
flag = True
return True二叉树中的最大路径和
问题描述
124. 二叉树中的最大路径和
路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次 。该路径至少包含一个 节点，且不一定经过根节点。路径和是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其最大路径和 。
示例：
输入： root = [-10，9，20，null，null，15，7]
输出：42
解释：最优路径是 15 -> 20 -> 7，路径和为42。
分析问题
首先，我们定义一个函数，来求二叉树中一个节点的最大的贡献值。具体来说，就是在以该节点为根节点的子树中，寻找以该节点为起点的一条节点值之和最大的路径。具体的计算方式如下。
- 如果节点为空，那么该节点最大贡献值为0。
- 如果节点非空，那么该节点的最大贡献值就等于节点值与其子节点中的最大贡献值之和（对于叶子节点，最大贡献值就等于节点值）
我们可以通过递归的方法求出二叉树中所有节点的贡献值。那我们该如何得到二叉树的最大路径和呢？其实，对于二叉树中的一个节点，包含该节点最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。我们可以维护一个全局变量max_value，在递归的过程中去更新max_value的值，最后得到的 max_value的值即为二叉树中的最大路径和。
下面我们来看一下该算法的实现。
class Solution:
def __init__(self):
self.max_value = float("-inf")
def maxPathSum(self, root):
#保存最大的路径和
#递归获得节点的最大贡献值
def max_gain(node):
#如果为空，最大贡献值为0
if not node:
return 0
#递归计算左右子节点的最大贡献值
#只有在最大贡献值大于0时，才会选取该子节点
left = max(max_gain(node.left), 0)
right = max(max_gain(node.right), 0)
#节点的最大路径和取决于该节点的值和该节点的左右子节点的最大贡献值
cur_path = left + node.val + right
#更新最大值
self.max_value = max(self.max_value, cur_path)
#返回节点的最大贡献值
return node.val + max(left, right)
#从根节点开始递归求解
max_gain(root)
return self.max_value该算法的时间复杂度和空间复杂度都是O(N)，其中N代表二叉树的节点个数。
判断二叉树是否对称
问题描述
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
示例：二叉树 [1, 2, 2, 3, 4, 4, 3] 是对称的，而二叉树[1, 2, 2, null, 3, null, 3] 则不是镜像对称的:
分析问题
首先，我们来看一下对称二叉树的定义。对称二叉树是指满足以下条件的二叉树：对于树中的任意两个对称节点L和R，一定有：
- L.val = R.val，即两个对称节点的值是相等的。
- L.left.val = R.right.val，即L的左子节点的值要和R的右子节点的值相等。
- L.right.val = R.left.val，即L的右子节点的值要和R的左子节点的值相等。
所以，我们可以从顶至底进行递归处理，然后判断每对节点是否对称，从而判断树是否为对称二叉树。
下面我们来看一下代码的实现。
class Solution:
def isSymmetric(self, root):
#如果为空树，直接返回True
if not root:
return True
#递归判断
def is_recur(L, R):
#如果同时到达叶子节点，则返回True
if not L and not R:
return True
#如果有一个到达叶子节点或者
#L和R的值不相等，代表不是对称的，返回False
if not L or not R or L.val != R.val:
return False
return is_recur(L.left, R.right) and is_recur(L.right, R.left)
#递归判断左右子节点
return is_recur(root.left, root.right)该算法的时间复杂度和空间复杂度都是O(N)，其中 N 为二叉树的节点数量。
序列化二叉树
问题描述
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例：
输入：root = [1，2，3，null，null，4，5]
输出：[1，2，3，null，null，4，5]
分析问题
我们都知道对于不同的二叉树进行先序、中序、后序或者层序遍历得到的遍历结果有可能是相同的，即如果知道了遍历序列，我们不能确定唯一的一颗二叉树，而题目要求的序列化和反序列化是一对可逆操作，即对一棵树进行序列化后，我们还能通过序列化后的结果反序列化还原成原来的那棵树。所以我们需要对二叉树的遍历过程改造一下，这里以层序遍历为例。在遍历的过程中，为了完整的表示二叉树，考虑将叶节点下的 null 也记录。下面我们来看一下具体的实现。
序列化
我们可以借助队列来实现二叉树的层序遍历，在层序遍历的过程中，我们把越过叶子节点的null也加入序列化的结果中。具体算法流程如下所示：
- 如果给定的二叉树为空，直接返回"[]"
- 初始化一个队列queue，并把根节点加入。
- 对二叉树进行层序遍历。当队列为空时跳出。
- 节点出队，记为node。
- 如果node不为空，将node.val加入结果列表中，并且将node的左、右子节点入队。如果node为空，将“null”加入结果列表中。
- 拼接结果列表，用
','隔开，首尾添加中括号，并将其返回。
反序列化
利用队列按层构建二叉树。具体算法流程如下所示：
- 如果data为空，直接返回null。
- 初始化列表vals（去掉首尾括号，再用逗号隔开），指针 i = 1 ，将根节点 root （值为 vals[0] ）入队；
- 按层构建二叉树，当队列为空时跳出；
- 节点出队，记为node。
- 构建 node 的左子节点，node.left 的值为 vals[i] ，并将 node.left 入队，然后执行 i=i+1。
- 构建 node 的右子节点，node.right 的值为 vals[i] ，并将 node.right 入队，然后执行 i=i+1。
- 返回根节点 root 即可。
下面我们来看一下代码的实现。
class Codec:
def serialize(self, root):
#如果二叉树为空，直接返回"[]"
if not root:
return "[]"
#初始化一个队列
queue = collections.deque()
#将根节点加入队列中
queue.append(root)
#结果列表
res = []
#记录null的个数，遇到非空节点就将之前的null节点加入到结果列表中
null_count=0
while queue:
node = queue.popleft()
if node:
#遇到非空节点就将之前的null节点加入到结果列表中
if null_count != 0:
res.extend(["null"] * null_count)
null_count=0
res.append(str(node.val))
#node的左、右子节点入队
queue.append(node.left)
queue.append(node.right)
else:
#记录null节点的个数
null_count=null_count+1
return '[' + ','.join(res) + ']'
def deserialize(self, data):
#如果data为"[]",代表二叉树是空，直接返回
if data == "[]":
return
#初始化
vals = data[1:-1].split(',')
i=1
#初始化根节点，并将其入队
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
while queue:
if i>=len(vals):
break
node = queue.popleft()
#添加左子节点
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if i>=len(vals):
break
#添加右子节点
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root二叉搜索树的第k个结点
问题描述
230. 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
’示例：
输入：{5,3,7,2,4,6,8},3
输出：4
说明：按结点数值升序顺序排序为[2,3,4,5,6,7,8]，可知第三小结点的值为4，所以返回4 。
分析问题
我们都知道对二叉搜索树进行中序遍历，得到的结果是升序排列的。因此我们可以利用此性质，对二叉搜索树执行中序遍历，并返回第k小的值即可。
class Solution:
def kthSmallest(self, root, k):
stack = []
while root or stack:
#一直遍历到二叉树的最左叶子节点
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
#如果已经遍历到第k个节点，直接返回
if k == 0:
return root.val
root = root.right如果给定的树是平衡树时，那时间复杂度取得最小值O(logN+k)，空间复杂度是O(logN)。如果树是线性树，即树中的每个结点都只有一个子结点或者没有子结点，此时时间复杂度是O(N+k)，空间复杂度是O(N)。
树的直径
给定一棵树，求出这棵树的直径，即树上最远两点的距离。
包含n个结点，n-1条边的连通图称为树。
示例1：
# 树的直径 # @param n int整型 树的节点个数 # @param Tree_edge Interval类一维数组 树的边 # @param Edge_value int整型一维数组 边的权值 # @return int整型 # class Solution: def solve(self , n , Tree_edge , Edge_value ): # write code here
输入：6 , [[0,1], [1,5], [1,2], [2,3], [2,4]], [3,4,2,1,5]，其中6表示树的节点个数，[[0,1], [1,5], [1,2], [2,3], [2,4]] 表示树的边，[3,4,2,1,5]表示边的权值。
输出：11
解释：示例1所表示的树的结构如下所示。
其中结点4到结点5之间的路径最长，是树的直径，距离为5+2+4=11。
分析问题
这道题是求多叉树的直径问题，我们可以把一颗树看成是没有环的无向图。那我们如何来求没有环的无向图的最长路径呢？在开始之前，我们需要引入一个定理：从图中的任何一点a出发，我们去寻找以该点为起点的最大路径，假设终点是t，那么t一定是我们所求的图的最长路径的其中的一个端点。下面我们来证明一下。
假设给定的无环的无向图的最长路径为s-t，其中s和t为两个端点。然后我们从图中的任意一点a出发，去寻找以a为起点的最长路径。
- 如果该路径没有经过s-t，那么与s-t是最长路径是相矛盾的。
- 如果经过路径s-t里的节点，但是没有沿着s-t这条路径走。我们假设a走到与s-t路径相交的节点前的路径长度为x1，沿着s-t路径走的话最长剩余的长度为x2，不沿着s-t路径走的最长剩余的长度为x3，s-t路径长度减去x2的长度为x4，则s-t的路径长度为x2+x4。根据 x1+x3 > x1+x2 可以推出 x3 > x2 ，从而得出 x2+x4 < x3+x4，这与s-t是最长路径相矛盾。
因此，我们可以通过两次深度优先搜索就可以求解。具体来说：
- 首先，根据连通关系以及边的权重构建无向图。
- 随机找一个顶点，利用深度优先搜索找到距离该点最远的顶点s，根据上述定理可以知道，该点一定是无向图中最长路径的其中一个端点。
- 然后以该点出发，利用深度优先搜索寻找最长路径，就是该无环无向图的直径。
下面我们来看一下代码的实现。
class Edge:
def __init__(self,end,w):
self.end=end
self.w=w
class Solution:
def solve(self,n,Tree_edge,Edge_value):
#根据父子关系和边的权重构建无线图，用邻接表来表示
graph={}
m=len(Tree_edge)
if len(Tree_edge)!=len(Edge_value) or m==0:
return 0
for i in range(0,m):
tree_edge=Tree_edge[i]
#边的起点和终点
start=tree_edge[0]
end=tree_edge[1]
#边的权重
w=Edge_value[i]
edge=Edge(end,w)
if not graph.keys().__contains__(start):
graph[start]=[]
graph.get(start).append(edge)
edge = Edge(start, w)
if not graph.keys().__contains__(end):
graph[end]=[]
graph.get(end).append(edge)
#其中res[0]表示最长路径的长度，res[1]代表最长路径的终点
res=[0,0]
#以0为起点，进行dfs搜索
self.dfs(graph, 0, -1, 0, res)
#以res[1]为起点，进行第二次dfs搜索
start=res[1]
res=[0, start]
self.dfs(graph, start, -1, 0, res)
#返回最长路径
return res[0]
def dfs(self,graph,source, pre, path_len,res):
edges=graph.get(source)
for edge in edges:
#防止往回走
if edge.end!=pre:
path_len=path_len+edge.w
#如果路径长度变长，则更新res
if path_len > res[0]:
res[0]=path_len
res[1]=edge.end
#继续dfs搜索
self.dfs(graph, edge.end, source, path_len, res)
#回溯
path_len = path_len-edge.w二叉树的镜像
问题描述
剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
示例：
输入：
4 / \ 2 7 / \ / \ 1 3 6 9
输出：
4 / \ 7 2 / \ / \ 9 6 3 1
分析问题
二叉树镜像是指对于二叉树中的任意节点 root ，假设其左、右子节点分别为left和right。则在镜像中对应的root节点，其左、右子节点分别为right和left。
我们可以使用递归法来求解。首先，从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root 的左右两棵子树都已经翻转得到镜像，那么我们只需要交换两棵子树的位置，即可得到以root为根节点的整棵子树的镜像。
class Solution:
def mirrorTree(self, root):
if not root:
return root
#递归的求左、右子节点的镜像
left = self.mirrorTree(root.left)
right = self.mirrorTree(root.right)
#交换左右子节点的位置
root.left, root.right = right, left
return root该算法的时间复杂度是O(N)，其中 N 为二叉树节点的数目。空间复杂度也是O(N)。
合并二叉树
问题描述
617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例：
输入：
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7 输出：
合并后的树:
3
/ \
4 5
/ \ \
5 4 7分析问题
首先我们来看一下如何合并两个数组，例如对数组a=[1,3,2,5]和数组b=[2,1,3,4,7]进行合并，我们只需要遍历数组，将数组b的值合并到数组a中，然后返回数组a即可。对于二叉树来说，也和数组类似，我们遍历二叉树的每个节点，将对应节点合并即可。
对于二叉树的遍历，我们既可以使用深度优先搜索，也可以使用广度优先搜索。我们先来看一下如何使用深度优先搜索来求解。具体来说就是从根节点开始同时遍历两颗二叉树，并将其对应的节点进行合并。两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
- 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
- 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
- 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和。
该节点合并完成后，我们接着递归的处理它的左右子节点，直到两棵树合并完成。
下面我们来看一下代码的实现。
class Solution:
def mergeTrees(self, t1, t2):
#如果一个节点为空，直接返回另一个
if not t1:
return t2
if not t2:
return t1
#合并两个节点
merged = TreeNode(t1.val + t2.val)
#递归合并左、右子节点
merged.left = self.mergeTrees(t1.left, t2.left)
merged.right = self.mergeTrees(t1.right, t2.right)
return merged将升序数组转化为平衡二叉搜索树
问题描述
108. 将有序数组转换为二叉搜索树
给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）。平衡二叉搜索树是指树上的每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1。
示例：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
分析问题
我们都知道对一颗二叉搜索树进行中序遍历，得到的序列是一个升序排列的。所以给定的数组是二叉搜索树的中序遍历结果。下面我们来看一下如何根据二叉搜索树的中序遍历来生成一颗高度平衡的二叉搜索树。
因为平衡二叉搜索树的左、右子树的节点数量之差不大于1。所以，我们可以选择数组中中间的数字作为二叉搜索树的根节点。这样就可以确保左右子树的节点个数之差不大于1，从而使得树时平衡的。如果给定的数组长度是奇数，则根节点的选择是唯一的，如果数组的长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的。
在确定了平衡二叉搜索树的根节点之后，其余的数字分别位于平衡二叉搜索树的左子树和右子树中，左子树和右子树分别也是平衡二叉搜索树，因此可以通过递归的方式创建平衡二叉搜索树。
根据选择根节点的不同，我们可以有三种方法来构造平衡二叉搜索树。
方法一
选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right) // 2。
class Solution:
def sortedArrayToBST(self, nums):
def cur(left, right):
if left > right:
return None
#选择中间位置左边的数字作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
#递归求解左右子树
root.left = cur(left, mid - 1)
root.right = cur(mid + 1, right)
return root
return cur(0, len(nums) - 1)方法二：
选择中间位置右边的数字作为根节点，则根节点的下标为 mid=(left+right+1) // 2。
class Solution:
def sortedArrayToBST(self, nums):
def cur(left, right):
if left > right:
return None
#选择中间位置右边的数字作为根节点
mid = (left + right + 1) // 2
root = TreeNode(nums[mid])
#递归求解左右子树
root.left = cur(left, mid - 1)
root.right = cur(mid + 1, right)
return root
return cur(0, len(nums) - 1)方法三
选择任意一个中间位置数字作为根节点，则根节点的下标mid在(left+right)//2 和 (left+right+1)/2 中随机选择一个。
import random
class Solution:
def sortedArrayToBST(self, nums):
def cur(left, right):
if left > right:
return None
#选择中间位置随机一个作为根节点
random_data= random.randint(0, 1)
mid = (left + right + random_data) // 2
root = TreeNode(nums[mid])
#递归求解左右子树
root.left = cur(left, mid - 1)
root.right = cur(mid + 1, right)
return root
return cur(0, len(nums) - 1)完全二叉树结点数
问题描述
222. 完全二叉树的节点个数
给你一棵完全二叉树的根节点 root ，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例：
输入：root = [1,2,3,4,5,6]
输出：6
分析问题
对于任意一颗二叉树来说，我们都可以使用深度优先搜索和广度优先搜索来计算节点的个数，其时间复杂度和空间复杂度都是O(n)。那对于一颗完全二叉树来说，有什么更好的求解方式吗？
根据完全二叉树的特征可知，完全二叉树的最左边的节点一定位于树的最后一层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为二叉树的最大层数。
我们假设完全二叉树的根节点位于第0层，完全二叉树的最大层数是h，当0<= i < h时，第i层包含2i个节点，最后一层包含的节点数为1~2h个节点。因此对于最大层数为h的完全二叉树来说，节点个数在[2h， 2h+1-1]范围内，我们可以在该范围内通过二分查找的方式得到完全二叉树的节点个数。
具体来说，我们可以在[2h， 2h+1-1]范围内进行二分查找。我们根据范围的上下界得到当前需要判断的节点个数 k，如果第 k个节点存在，则节点个数一定大于或等于 k，如果第 k个节点不存在，则节点个数一定小于 k，由此可以将查找的范围缩小一半，直到得到节点个数。
下面我们来看一下如何判断第k个节点是否存在？
假设第k个节点位于第h层，则数k的二进制表示包含h+1位，其中最高位是1，其余各位从高到低表示从根节点到第 k个节点的路径，0 表示移动到左子节点，1 表示移动到右子节点。通过位运算得到第 k个节点对应的路径，通过判断该路径对应的节点是否存在，即可判断第 k 个节点是否存在。
下面我们来看一下代码的实现。
class Solution:
def countNodes(self, root):
if not root:
return 0
#求数的层数
level=0
node=root
while node.left:
level=level+1
node=node.left
#完全二叉树的节点个数范围是[2^h,(2^h+1)-1]
low=2**level
high=2**(level+1)-1
#二叉查找
while low<high:
mid=(low+high+1)//2
#判断结点是否存在，如果存在，
#则节点数在[mid,high]范围中，否则在[low,mid-1]
if self.exist(root,level,mid):
low=mid
else:
high=mid-1
return low
def exist(self,root,level,k):
#bits用来控制判断走到了对应的二进制的哪一位
#比如要判断节点5是否存在，它对应的二进制是101，我们把最高位去掉，从第二位开始判断
#所以我们需要一个bits为010和它求与，即010 & 101，发现第二位是0，说明从根节点开始，第一步向左走
#然后bits右移一位，变成了001，然后继续求与，即 001 & 101，发现第三位是1，所以向右走。
#最后bit为0，说明已经找到编号为5的这个节点相对于根节点的位置
#看这个节点是不是空，exist返回true，如果是空，exist返回false
bits= 1 << (level-1)
node=root
while node and bits > 0:
if bits & k == 0:
node=node.left
else:
node=node.right
bits >>=1
return node!=None#面试高频考点汇总##学习路径#
腾讯公司福利 465人发布