力扣 二叉树 算法+题目 整理

二叉树基础

包括三种遍历，建树和遍历的方法。

二叉树遍历

力扣 144,94,145 二叉树前中后序遍历

使用递归或者迭代空间复杂度都是o(n)，而通过morris遍历则可以达到o(1)，其介绍在Morris遍历 介绍+前中后序遍历

103. 二叉树的锯齿形层序遍历

锯齿遍历需要左右左右方向变化，编写并不难，注意内存的优化

107. 二叉树的层序遍历 II

输出自底向上的遍历结果，和上一题很类似。

116. 填充每个节点的下一个右侧节点指针

在每层，从左到右添加next的指向，最优的方法是通过dummy节点。

二叉树构建

先序和中序，中序和后序都可以确定一棵树，但是先序和后序确定的树不唯一。

105. 从前序与中序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

889. 根据前序和后序遍历构造二叉树

二叉树性质

力扣 100.相同的树

判断两棵树是否相同，注意c++节点p判空的条件是if(!p)

力扣 101. 对称二叉树 [递归+迭代]

判断二叉树是否轴对称，可以使用递归方法（可参考 上一题），也可以利用队列将递归转化为迭代（其余题目也可以这样）。

力扣 104. 二叉树的最大深度

计算二叉树的最大深度，此处计算深度的方法可以给下题做参考。

力扣 110. 平衡二叉树 [基础+优化]

判断是否是平衡二叉树（定义：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ）。

此题需要利用计算深度的方法，同时基础解法会产生大量冗余计算，优化代码提供了实例可以了解优化过程。

力扣 111. 二叉树的最小深度 [递归+迭代]

计算最小深度，可以参考最大深度的题，可是需要有变动。

力扣 662. 二叉树最大宽度

计算最大宽度，注意数值类型，使用迭代求解可以利用vector优化数据结构。

二叉树路径求和

力扣 112. 路径总和

找一条根到叶子的路径，节点值的总和要满足目标，

力扣 113. 路径总和 II [dfs,bfs]

是上一题的变种

力扣 124. 二叉树中的最大路径和 [1.0,2.0]

这一题题意不难理解，但转化为代码整理好思路

力扣 129. 求根节点到叶节点数字之和

力扣 257. 二叉树的所有路径

原文地址：http://www.cnblogs.com/fudanxi/p/16659261.html