求二叉树是否相同？
用递归法 ，传入左右两棵树的根节点 ，然后比较 left.left == right.left; 以及 left.right ==right.right;
这是递归里面的内容
递归结束的条件：
代码语言：javascript复制class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if( p == null && q == null){
return true ; // 这样的情况下就可以返回true了
}else if ( p != null && q == null){
return false;
}else if( p == null && q != null ){
return false;
}else if (p.val != q.val){
return false;
}else{
//递归的内容
boolean b1 = isSameTree(p.left , q.left);
boolean b2 = isSameTree(p.right ,q.right);
boolean b = b1 && b2;
return b;
}
}
}求二叉树是否对称 ？
代码语言：javascript复制class Solution {
//这里我们用队列来实现，思路：
//将左右子树分开，然后分别以左右为树比较
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}else{
return isTrue(root.left , root.right);
}
}
public boolean isTrue(TreeNode left, TreeNode right){
if(left == null && right == null){
return true;
}else if(left == null || right == null){
return false;
}else if(left.val != right.val ){
return false;
}
else{
return isTrue(left.left,right.right) && isTrue(left.right , right.left);
}
}
}求完全二叉树的节点数
方法一 ： 最原始的方法， 用迭代法或者递归的方法将二叉树遍历完，得出节点的数量
方法二 ： 只针对完全二叉树的解法
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
按照这个完全二叉树的特征。我们就可以确定一个终止条件
代码语言：javascript复制if(leftDepth == rightDepth){
return 2<<leftDepth - 1;
}完全二叉树只有两种情况
情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
- 对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
- 对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来 计算。
所以说如果整棵树不是满二叉树的话，那么就递归他的左右孩子，直到递归到某棵子树 ，它（子树）是满二叉树， 那么就达到递归截至的条件 ，输出节点数。
代码语言：javascript复制class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
TreeNode leftD = root.left;
TreeNode rightD = root.right;
int rD = 0;
int lD = 0;//初始化为0 是为了后面求指数方便
//求左右子树的深度
while(leftD != null){
leftD = leftD.left;
lD ;
}
while(rightD != null){
rightD = rightD.right;
rD ;
}
//如果判断该树是满二叉树那么直接输出即可
if(rD == lD){
return (2 << lD) - 1; // 2^n - 1
}
//继续递归，计算完左右子树的节点，然后再加上根节点;
lNum = countNodes(root.left);
rNum = countNodes(root.right);
return lNum rNum 1;
}
}总结 ：对于这个二叉树来说，他没有遍历所有的节点，如果说一个节点的子树他是满二叉树，那么就只需要用2 << n - 1这个公式就能算出这个子树的所有节点。
平衡二叉树
一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
求解高度用后序遍历 ， 求解深度用前序遍历
【因为后序是根据左右孩子的高度，然后父节点再根据左右孩子节点的情况进行 1 ===》》》层层向上返回 】
【前序求解的深度 ，顺序是 [中左右]一直向下遍历，不向上返回结果。符合一直向下统计节点的深度 】
代码语言：javascript复制class Solution {
public boolean isBalanced(TreeNode root) {
int res = isTree(root);
return res == -1 ? false : true;
}
//先定义一个方法判断平衡二叉树
public int isTree(TreeNode node){
if(node == null){
return 0;
}
int ll = isTree(node.left);
if(ll == -1){
return -1;
}
int rl = isTree(node.right);
if(rl == -1){
return -1;
}
//判断是否满足平衡二叉树的条件
if(Math.abs(ll-rl) > 1){
return -1;
}
//返回平衡二叉树的高度
return Math.max(ll,rl) 1;
}
}求解深度的方法(c 实现)
代码语言：javascript复制class Solution {
public:
int result;
void getDepth(TreeNode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { // 左
depth ; // 深度 1
getDepth(node->left, depth);
depth--; // 回溯，深度-1
}
if (node->right) { // 右
depth ; // 深度 1
getDepth(node->right, depth);
depth--; // 回溯，深度-1
}
return ;
}
int maxDepth(TreeNode* root) {
result = 0;
if (root == 0) return result;
getDepth(root, 1);
return result;
}
};二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。
- 创建路径集合path 以及 结果集合list。用于存储路径与最后的结果
- 前序遍历 ，先将父节点加入到路径集合path中
- 递归结束的条件 –> 到叶子节点 （如图的 4 号节点）
- 递归结束，回溯之前。将该路径保存到结果路径中
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
//用递归 ，前序遍历
List<String> list = new ArrayList<>();
if(root == null){
return list;
}
List<Integer> path = new ArrayList<>();
prefix(root,path,list);
return list;
}
public void prefix(TreeNode node , List<Integer> path, List<String> list){
//先将该节点保存到路径
path.add(node.val);
//如果到叶子节点就结束本次递归
if(node.left == null && node.right == null){
//StringBuffer用于拼接路径
StringBuffer sb = new StringBuffer();
//循环拼接路径
for(int i=0 ;i<path.size() - 1 ;i ){
//因为当前的节点都已经保存到了path中，所以这里只需要循环按要求拼接即可
sb.append(path.get(i)).append("->");
}
/*
因为最后循环结束时如果我们将最后一个节点也拼接进入 ，那么势必会多出来一个‘->’这就与题目要求的不符合
所以我们将最后一个节点放到循环外面拼接
*/
sb.append(path.get(path.size()-1));
//将拼接好的路径保存起来
list.add(sb.toString());
// 结束本次递归
return;
}
if(node.left != null){
prefix(node.left , path ,list);
//递归结束 ，回溯时删除最后一个节点，【1-> 2 -> 5】路径就会变成【1 -> 2 -> 】
//这样下次递归就会从【2】节点开始
path.remove(path.size() - 1 );
}
if(node.right != null){
prefix(node.right , path , list);
path.remove(path.size() - 1);
}
}
}获取树最左下角的节点的值
代码语言：javascript复制//方法一 ； 递归法
class Solution {
public int res = 0;
public int depth = - 1;
public int findBottomLeftValue(TreeNode root) {
if(root == null){
return 0;
}
GetLeft(root,1);
return res;
}
public void GetLeft(TreeNode root , int deep){
if(root.left == null && root.right == null){
if(deep > depth){
depth = deep;
res = root.val;
}
}
if(root.left != null){
GetLeft(root.left , deep 1);
}
if(root.right != null){
GetLeft(root.right, deep 1);
}
}
}
//方法二 ： 迭代法
*/
class Solution {
List<List<Integer>> list = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null){
return 0;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
List<Integer> nodeList = new ArrayList<>();
for(int i= 0 ;i<size;i ){
TreeNode node = que.poll();
nodeList.add(node.val);
if(node.left != null){
que.offer(node.left);
}
if(node.right != null){
que.offer(node.right);
}
}
list.add(nodeList);
}
return list.get(list.size()- 1).get(0);
}
}
//迭代法二 ：
//迭代法
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int res = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ) {
TreeNode poll = queue.poll();
if (i == 0) {
res = poll.val;
}
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
}
return res;
}
}路径总和二
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
代码语言：javascript复制class Solution {
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root== null){
return list;
}
List<Integer> path = new ArrayList<>();
prefix(root,path,targetSum);
return list;
}
public void prefix(TreeNode root, List<Integer> path,int targetSum){
path.add(root.val);
if(root.left == null && root.right == null){
List<Integer> alist= new ArrayList<>();
for(int i= 0;i<path.size();i ){
alist.add(path.get(i));
}
int size = alist.size();
int sum = 0;
for(int j =0;j<size;j ){
sum = alist.get(j);
}
if(sum == targetSum){
list.add(alist);
}
}
if(root.left != null){
prefix(root.left , path, targetSum);
path.remove(path.size()-1);
}
if(root.right != null){
prefix(root.right , path, targetSum);
path.remove(path.size()-1);
}
}
}从中序与后序构建二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1]输出：[-1]
思路
- 判断数组是否为空 ！
- 不为空则向下继续，为空返回null
- 去后序数组中的最后一个元素为树的头节点的val值，（原因由后序遍历可知）
- 切割中序数组 ，以头节点的val值为区分（作为切割点） ，切割成中序左数组 和 中序右数组
- 切割后序数组， 切成后序左数组 和后序右数组
- 递归处理左右区间
代码实现（复杂易懂）
代码语言：javascript复制class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length == 0 || postorder.length == 0){
return null;
}
int rootVal = postorder[postorder.length - 1];
TreeNode node = new TreeNode(rootVal);
int inSize = inorder.length;
int postSize = postorder.length;
int mid;
for(mid = 0; mid < inSize;mid ){
if(inorder[mid] == rootVal){
break;
}
}
//切割中序
int inBegin = 0;
int inEnd = mid;
int[] newIn = Arrays.copyOfRange(inorder,inBegin,inEnd);
int[] newPost = Arrays.copyOfRange(postorder,inBegin,inEnd);
node.left = buildTree(newIn,newPost);
int postBegin = mid 1 ;
int postEnd = postorder.length - 1;
int[] newIn2 = Arrays.copyOfRange(inorder , postBegin , inSize);
int[] newPost2 = Arrays.copyOfRange(postorder,mid, postEnd);
node.right = buildTree(newIn2,newPost2);
return node;
}
}代码实现（简易map版）
代码语言：javascript复制class Solution {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i ) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = findNode(inorder, inBegin, rootIndex,
postorder, postBegin, postBegin lenOfLeft);
root.right = findNode(inorder, rootIndex 1, inEnd,
postorder, postBegin lenOfLeft, postEnd - 1);
return root;
}
}从前序与中序构建二叉树
思路
与从中序和后序构建二叉树相同
代码实现
代码语言：javascript复制class Solution {
Map<Integer, Integer> map; // 方便根据数值查找位置
public TreeNode buildTree(int[] inorder, int[] postorder) {
map = new HashMap<>();
for (int i = 0; i < inorder.length; i ) { // 用map保存中序序列的数值对应位置
map.put(inorder[i], i);
}
return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开
}
public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
// 参数里的范围都是前闭后开
if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点
int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数
root.left = findNode(inorder, inBegin, rootIndex,
postorder, postBegin, postBegin lenOfLeft);
root.right = findNode(inorder, rootIndex 1, inEnd,
postorder, postBegin lenOfLeft, postEnd - 1);
return root;
}
}参考说明（感谢！）：
力扣！
代码随想录！
