目录
100. 相同的树
101. 对称二叉树(镜像对称)
104 二叉树的最大深度
平衡二叉树
翻转二叉树
二叉树的坡度
617 合并二叉树
654. 最大二叉树
965. 单值二叉树
二叉树剪枝
递归查找树
100. 相同的树
/**
* 100. 相同的树
* 用了先序遍历
* 也可以用后序 和中序
* 遍历两个二叉树是否相同
*/
public class isSameTree {
//递归版实现
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}
if(p==null || q==null) //防止出现空指针的空指针 如果此时p为空，下面会调用p.val 就会报空指针异常
return false;
// if(p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){
// return true;
// }else{
// return false;
// }
return p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
// //迭代版实现
// public boolean isSameTree(TreeNode p,TreeNode q){
// Stack<TreeNode> stack = new Stack<TreeNode>();
// stack.push(p);
// stack.push(q);
// while(!stack.empty()){
// TreeNode t1 = stack.pop();
// TreeNode t2 = stack.pop();
// if(t1==null && t2 == null)
// continue;
// if(t1==null || t2==null || t1.val!=t2.val ) //t.val要放在t2.val的后面 防止出现空指针异常
// return false;
// if(t1.val==t2.val){
// stack.push(t1.left);
// stack.push(t2.left);
// stack.push(t1.right);
// stack.push(t2.right);
// }
// }
// return true;
// }
}
101. 对称二叉树(镜像对称)
/**
*101. 对称二叉树
* 给定一个二叉树，检查它是否是镜像对称的。
* 思路 ：
* 就是
* 后序遍历 ：遍历第n个结点的关系 首先要知道所有第n-1个结点的情况
* 先序遍历 ：先知道了第n个节结点的关系后，然后再进入第n-1个结点的情况
* 中序遍历 : 先了解第 左 n-1个结点的关系 ，然后再进入第n个结点，再了解右n-1个结点的关系
* 二叉树的先根遍历（最好的情况就是一开始的根结点就不同）二叉树的后序遍历（最好的情况是一开始根节点相同，但是有
* 空结点的情况出现） 效率应该是一样的
* 利用树的先根遍历，先遍历两颗树的根节点是否相同
* 比较左子树的右结点与右子树的左结点是否相同
* 比较右子树的右结点与左子树的左结点是否相同
*
*/
public class isSymmetric {
public boolean isSymmetric(TreeNode root) {
// if(root==null){ //这部多余了 直接递归进入就行了
// return true;
// }
// TreeNode root_left = root.left;
// TreeNode root_right = root.right;
// return dfs(root_left,root_right);
return dfs(root,root);
}
public boolean dfs(TreeNode root_left, TreeNode root_right){
if(root_left==null && root_right==null){
return true;
}else if(root_left==null || root_right==null){
return false;
}
return root_left.val==root_right.val
&& dfs(root_left.right,root_right.left)
&& dfs(root_left.left,root_right.right);
}
}
104 二叉树的最大深度
public class MaxDepth {
//此方法是后序遍历方式，想要知道第n个结点的高度 首先知道第n-1个结点的高度，然后再加上1
//先序遍历就是先定义 根的高度为1
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
else {
int lh = maxDepth(root.left) + 1;
int rh = maxDepth(root.right) + 1;
return Math.max(lh, rh);
}
}
}
平衡二叉树
/**
* 这道题 的static考察 还行，static是一块被共用的内存
* 多组输入会改变static的值
* 因此在调用方法时初始化static中的值
* 给定一个二叉树，判断它是否是高度平衡的二叉树。
*
* 本题中，一棵高度平衡二叉树定义为：
*
* 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
* 思路：
* 就是当左右子树的绝对值差超过1的时候就使全局变量flag变为
* false,
* 当要知道第n个结点的高度，需要知道左子树的高度和右子树的高度
* 取左子树和右子树的高度 递归的返回条件，当树的结点为空时，
* 就返回0，
* 这道题可以剪枝 不需要一直遍历，当找到了大于2的结点后 就可以直接返回了
*
*/
public class IsBalanced {
static boolean flag = true;
public boolean isBalanced(TreeNode root) {
//这个地方是防止连续数据
flag=true;
bfs_height(root);
return flag;
}
int bfs_height(TreeNode root){
if(root==null || !flag)
return 0;
int h1=bfs_height(root.left)+1;
int h2 = bfs_height(root.right)+1;
if(Math.abs(h1-h2)>=2)
flag=false;
return Math.max(h1,h2);
}
}
翻转二叉树
/**
* 翻转二叉树
*将左右结点进行交换
*
*/
class invertTree{
//递归实现 交换了结点后 进入下一次递归
//在递归开始时就进行交换
public TreeNode invertTree(TreeNode root) {
if(root==null)
return null;
else{
TreeNode temp = root.left;
root.left=root.right;
root.right =temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
//在递归返回时进行交换
// public TreeNode invertTree(TreeNode root) {
// if(root==null)
// return null;
// else{
// TreeNode temp = root.left;
// root.left=invertTree(root.right);
// root.right=invertTree(temp);
//
// return root;
// }
// }
}
二叉树的坡度
/**
* 给定一个二叉树，计算整个树的坡度。
*
* 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
*
* 整个树的坡度就是其所有节点的坡度之和。
*
* 思路：要求坡度值和，只需要定义一个全局变量来保存每个结点的坡度值
* 因此问题化简为求出结点的坡度值
* 求第n个结点的坡度值，首先要知道第n个结点的左子树的值与右子树的值
* 而要知道这两者的值，就是知道 左子树n-1结点左子树的和 + n-1结点的值
* 右子树也同样如此
*/
public class FindTilt {
static int sum =0;
public int findTilt(TreeNode root) {
sum=0;
dfs(root);
return sum;
}
int dfs(TreeNode root){
if(root ==null)
return 0;
int left = dfs(root.left);
int right = dfs(root.right);
sum+=Math.abs(left-right);
return left + right + root.val;
}
}
617 合并二叉树
/**
* 617 合并二叉树
* 思路 ：
* 利用了后序遍历
* 当要合并第n个结点时 ，此时需要合并第 n - 1 个结点
* 将其中一颗树作为返回条件 例如将 树t1 作为返回条件
*/
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
// if(t1==null && t2 ==null) //这步判断可以省略了，下面两个判算不会报空指针异常
// return null;
if(t1==null)
return t2;
if(t2==null)
return t1;
else{
t1.left=mergeTrees(t1.left,t2.left); //也可以写成先序遍历的形势
t1.right=mergeTrees(t1.right,t2.right);
t1.val+=t2.val;
return t1;
}
}
654. 最大二叉树
/**
* 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
*
* 二叉树的根是数组中的最大元素。
* 左子树是通过数组中最大值左边部分构造出的最大二叉树。
* 右子树是通过数组中最大值右边部分构造出的最大二叉树。
*
* 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
* 654. 最大二叉树
* 思路 就是通过找到最大值的下标，然后分别遍历左边右边，
* 进行递归
* 递归返回条件是：当数组元素 的 起始点和末尾位置相等 直接返回
*/
public class constructMaximumBinaryTree {
public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode root=null;
root=null;
int length = nums.length;
return dfs(0,length,nums,root);
}
TreeNode dfs(int s,int e,int[] nums,TreeNode root){
if(s==e)
return null;
int maxIndex=s;
for(int i=s+1;i<e;i++){
if(nums[maxIndex]<nums[i]){
maxIndex=i;
}
}
root=new TreeNode(nums[maxIndex]);
root.left = dfs(s,maxIndex,nums,root.left);
root.right = dfs(maxIndex+1,e,nums,root.right);
return root;
}
965. 单值二叉树
/** * 965. 单值二叉树 * 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。 * * 只有给定的树是单值二叉树时，才返回 true；否则返回 false。 * * 此题思路 用了二叉树的先根遍历（判断第一个点是否与指定值相同，如果相同就进入左子树，和右子树） 也可用二叉树的 * 后序遍历 和中序遍历 ，但是时间复杂度可能会变高， 因为当根结点不同的时候，其实就可以直接退出了 */
public class isUnivalTree {
public boolean isUnivalTree(TreeNode root) {
if(root==null) return true;
int val = root.val;
return dfs(root,val);
}
public boolean dfs(TreeNode tree,int val){
if(tree==null) return true;
if(tree.val!=val) return false;
else{
return dfs(tree.left,val) && dfs(tree.right,val);
}
}
}
二叉树剪枝
/**
* 给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
*
* 返回移除了所有不包含 1 的子树的原二叉树。
*
* ( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
*
* 思路 就是删除掉只包含 0 结点的子树
* 直接从树的底部开始删除，当左右子树为null 结点为0就删除结点
*/
public TreeNode pruneTree(TreeNode root) {
prune(root);
return root;
}
boolean prune(TreeNode root){
if(root==null){
return true;
}
boolean left = prune(root.left);
boolean right = prune(root.right);
if(left)
root.left=null;
if(right)
root.right=null;
return left && right && root.val ==0;
}
递归查找树
/** *897. 递增顺序查找树 * 给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。 * 思路 通过中序遍历将结点放入数组中 * 再重新构建树 * 存在更好的思路，再递归的时候就重新构建树 */
static int[] arr=new int[100];
static int i =0;
public TreeNode increasingBST(TreeNode root) {
arr = new int[100];
i=0;
dfs(root);
TreeNode dummy = new TreeNode(0);
TreeNode first = dummy;
for(int j=0;j<i;j++){
first.right = new TreeNode(arr[j]);
first = first.right;
}
return dummy.right;
}
void dfs(TreeNode root){
if(root == null)
return ;
dfs(root.left);
arr[i++]=root.val;
dfs(root.right);
}
/** 此方法很巧妙 原帖 https://leetcode.com/problems/increasing-order-search-tree/discuss/165885/C++JavaPython-Self-Explained-5-line-O(N) 在递归过程中重构树 而不是重新放入数组中构建树 最后将相对最左的结点返回 设定一个尾巴结点，左孩子节点的尾巴结点是父节点 右孩子的尾巴结点为父节点的尾巴结点 返回的时候 根据中序遍历先返回相对最左边位置孩子结点（如果只有自己，左结点就是空，左结点的父节点就返回本身） 此时根据题意要将该结点的左结点置空 至于此结点的右孩子结点就要与此时相对最左的结点的根节点的尾巴结点相连（父节点的尾巴结点） **/
class Solution {
public TreeNode increasingBST(TreeNode root) {
return increasingBST(root,null);
}
public TreeNode increasingBST(TreeNode root,TreeNode tail){
if(root==null)
return tail;
TreeNode ret = increasingBST(root.left,root);
root.left=null;
root.right = increasingBST(root.right,tail);
return ret;
}
}
