求二叉树是否相同?

用递归法 ,传入左右两棵树的根节点 ,然后比较 left.left == right.left; 以及 left.right ==right.right;

这是递归里面的内容

递归结束的条件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}
}
}

求二叉树是否对称 ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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) 个节点

按照这个完全二叉树的特征。我们就可以确定一个终止条件

1
2
3
if(leftDepth == rightDepth){
return 2<<leftDepth - 1;
}

完全二叉树只有两种情况

情况一:就是满二叉树,情况二:最后一层叶子节点没有满。

  1. 对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。
  2. 对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来 计算。

img

所以说如果整棵树不是满二叉树的话,那么就递归他的左右孩子,直到递归到某棵子树 ,它(子树)是满二叉树, 那么就达到递归截至的条件 ,输出节点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 ===》》》层层向上返回 】

【前序求解的深度 ,顺序是 [中左右]一直向下遍历,不向上返回结果。符合一直向下统计节点的深度 】

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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++ 实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}
};

二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。

在这道题目中将第一次涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。

img

求二叉树的所有路径思路(草图)

img

  1. 创建路径集合path 以及 结果集合list。用于存储路径与最后的结果
  2. 前序遍历 ,先将父节点加入到路径集合path中
  3. 递归结束的条件 –> 到叶子节点 (如图的 4 号节点)
  4. 递归结束,回溯之前。将该路径保存到结果路径中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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);
}
}
}

获取树最左下角的节点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//方法一 ; 递归法

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:

img

输入: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:

img

输入:root = [1,2,3], targetSum = 5

输出:[]

示例 3:

输入:root = [1,2], targetSum = 0

输出:[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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:

img

输入:inorder = [-1], postorder = [-1]输出:[-1]

思路

  1. 判断数组是否为空 !
  2. 不为空则向下继续,为空返回null
  3. 去后序数组中的最后一个元素为树的头节点的val值,(原因由后序遍历可知)
  4. 切割中序数组 ,以头节点的val值为区分(作为切割点) ,切割成中序左数组 和 中序右数组
  5. 切割后序数组, 切成后序左数组 和后序右数组
  6. 递归处理左右区间

思维图

img

代码实现(复杂易懂)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}
}

从前序与中序构建二叉树

思路

与从中序和后序构建二叉树相同

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}
}

参考说明(感谢!):

力扣!

代码随想录!