二叉树

几秒前	#124 二叉树中的最大路径和	困难	1 次
8 分钟前	#236 二叉树的最近公共祖先	中等	2 次
16 分钟前	#437 路径总和 III	中等	1 次
1 小时前	#105 从前序与中序遍历序列构造二叉树	中等	1 次
2 小时前	#114 二叉树展开为链表	中等	1 次
2 小时前	#199 二叉树的右视图	中等	1 次
2 小时前	#230 二叉搜索树中第K小的元素	中等	1 次
5 小时前	#98 验证二叉搜索树	中等	7 次
5 小时前	#108 将有序数组转换为二叉搜索树	简单	1 次
6 小时前	#543 二叉树的直径	简单	2 次
6 小时前	#101 对称二叉树	简单	4 次
6 小时前	#226 翻转二叉树	简单	1 次
6 小时前	#104 二叉树的最大深度	简单	3 次
7 小时前	#102 二叉树的层序遍历	中等	1 次
7 小时前	#94 二叉树的中序遍历	简单	1次

二叉树备注：

1、二叉树的最大深度可以用递归

2、二叉树直径最后返回条件 +1 注意

3、前中构造二叉树的递归条件

4、路径总和3 这个要max 跟 0比较，最后返回要加上当前节点的值

5、

# 二叉树遍历（前、中、后）

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
    }
}
思路：
  1、递归
  2、前：左根右 中：根左右  后：左右根

1
2
3
4
5
6
7
8
9

# 层序遍历

class Solution {
    public List<List<Integer>> inorderTraversal(TreeNode root) {
    }
}
思路：
  1、利用queue，如果root不为空放进去
  2、while循环开始对queue不为空判断
  3、定义item的过程list用于存储每层的数据
  4、for循环来取queue的值 i为queue的size， 采用i--的形式，然后queue采取poll的方式弹出值，并将弹出的值放入item
  5、之后对弹出值的left和right进行判断，不为空的话 放入queue，方便进行下次循环
  6、之后将item放入 最终的res中
  7、最后返回res

1
2
3
4
5
6
7
8
9
10
11
12

# 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
    }
}
思路：
  1、递归
  2、递归终止条件判断 root 为null 返回root
  3、root的left 赋值给中间变量item
  4、root的left = 其right
  5、right等于item
  5、递归左子树
  6、递归右子树
  7、返回 root

1
2
3
4
5
6
7
8
9
10
11
12
13

# 对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
    }
}
思路：
  1、需要单独定义方法递归，传值分别为 root的左子树跟右子树
  2、新的compare方法内部逻辑为： 
  		a、如果 l跟r都为空 返回true；
  		b、如果 l跟 r 任何一个为空 返回false；（两个if判断）
  		c、如果 l跟r的val 不相等也是 false；
  		d、之后分别对l 跟 r 递归 得到 ln 跟 rn
  		e、最后返回 ln && rn
	3、返回 compare 方法

1
2
3
4
5
6
7
8
9
10
11
12
13

# 二叉树直径

class Solution {
    private int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
    }
}
思路：
  1、外层定义返回结果，然后单独定义一个process方法
  2、递归终止条件判断 root == null 返回0
  3、之后分别递归 left 跟 right  得到 l 跟 r 
  4、res 就为 l+r+1跟 原来 res的最大值    res = Math.max(res, l+r+1);
  5、最后返回 l跟r的最大值 +1 用于下次递归  Math.max(l, r)+1;

1
2
3
4
5
6
7
8
9
10
11
12

# 将有序数组转化为二叉树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
    }
}
思路：
  1、采用二分法 中间节点作为root节点
  2、定义新方法 process 传值分别为( num  ,l 开始0,  r 结束为num的长度-1)
  3、新方法内  如果 l  > r 返回null，说明当前节点为null
  4、之后 采用 （l+r+1)/2 的形式 找到mid 
  5、定义新的树  root 其val就是这个mid
  6、root的left采用递归，数组传进去， 开始 为l 结束为 mid-1
  7、right 同上 但开始为mid +1 结束为 r
  8、返回 root；
  9、最终返回process方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
    }
}
思路：
  1、定义一个新的process方法  传参为 root  Long最小值 l， 最大值 r
  2、方法内部 root为null 返回true
  3、得到当前节点的root的val
  4、此val 必须比 l大 r小  得到两个boolean 的判断
  5、然后 递归比较root的left跟right  传参分别是 root.left, l, mid    root.right, mid, r 同样得到两个Boolean的判断
  6、最后这四个进行 && 返回

1
2
3
4
5
6
7
8
9
10
11

# 二叉树中第k个最小的元素

class Solution {
    public int kthSmallest(TreeNode root, int k) {
    }
}
思路：
  1、遍历二叉树得到 list
  2、进行list的排序
  3、返回第k个值

1
2
3
4
5
6
7
8

# 二叉树右视图

class Solution {
    // 层序遍历的变种
    public List<Integer> rightSideView(TreeNode root) {
      
    }
}
思路：
  1、直接进行层序遍历
  2、不同： 放入res时 去最后一个元素放入

1
2
3
4
5
6
7
8
9

# 二叉树展开为链表

class Solution {
    List<TreeNode> res = new ArrayList<>();
    public void flatten(TreeNode root) {
    }
}
思路：
  1、定义新方法，先进行前序遍历  得到res
  2、对res开始从i=1遍历
  3、得到 l的值为get(i-1) r为 get（i）
  4、然后将l的left赋值为null l的right赋值为r

1
2
3
4
5
6
7
8
9
10

# 根据前序中序构造二叉树

class Solution {
    int[] preorder;
    Map<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++){
            dic.put(inorder[i], i);
        }
        return process(0, 0, inorder.length - 1);
    }
    public TreeNode process(int root, int left, int right) {
        if (left > right){
          	return null;   																			// 递归终止
        }                        
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + 1 + i - left , i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }
}
思路：
  1、先将前序放到外层  方便下面process处理
  2、再将中序缓存到外部的map中 方便赋值
  3、在进行递归处理 传参 root 0 left 0 right inorder.length - 1 ， 因为中序遍历可以确定right
  4、process内 逻辑如注释

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 int pathSum(TreeNode root, int sum) {
        // key是前缀和, value是大小为key的前缀和出现的次数
        Map<Long, Integer> prefixSumCount = new HashMap<>();
        // 前缀和为0的一条路径
        prefixSumCount.put(0L, 1);
        // 前缀和的递归回溯思路
        return process(root, prefixSumCount, sum, 0L);
    }


    private int process(TreeNode node, Map<Long, Integer> prefixSumCount, int target, long currSum) {
        // 1.递归终止条件
        if (node == null) {
            return 0;
        }
        // 2.本层要做的事情
        int res = 0;
        // 当前路径上的和
        currSum += node.val;

        //---核心代码
        // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径
        // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
        // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
        res += prefixSumCount.getOrDefault(currSum - target, 0);
        // 更新路径上当前节点前缀和的个数
        prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);
        //---核心代码

        // 3.进入下一层
        res += recursionPathSum(node.left, prefixSumCount, target, currSum);
        res += recursionPathSum(node.right, prefixSumCount, target, currSum);

        // 4.回到本层，恢复状态，去除当前节点的前缀和数量
        prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);
        return res;
    }
}
思路：
  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

# 最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    }
}
思路：
  1、如果root为空 以及 root== p或者 root== q 直接返回root
  2、然后直接递归 root 左和右 p和q都是原值传入
  3、比较：l为空 返回r r为空返回l  如果都没有为空 则返回root