树
这段时间刷了数据结构中”树“的算法,刷了有10多题了,想想刷完之后很容易忘,不能一直输入然后不输出,需要写一篇博客记录一下,自己也输出一些东西
102. 二叉树的层序遍历
用到了队列的数据结构来实现二叉树的层次遍历,Code0104是其他二叉树算法的基础,学会了它再稍作拓展就能解决一些其他的二叉树问题,如Code0101对称的二叉树,在层次遍历中对比队列中的
对称节点是否相同,再如Code0104求二叉树的最大深度
101. 对称二叉树
题目大意:给定一个二叉树,检查它是否是镜像对称的。
除了上述的层次遍历中对比对称节点是否相同的方式
还有一种递归的写法
按照递归三部曲的思路
- 首先确定递归函数名、返回值、参数,可以先拟定,后续需要时再做更改
- 然后确定递归的边界条件,比如这题需要知道二叉树是否对称,我们的边界条件就是对称与不对称的各种情况的合集
- 最后确定递归体------我在何时何地调用我自己,套娃问题
/**
* 解法一:递归法
* 难点就是在于要明白用什么遍历方式。
* 后续遍历
* 左右中
* 右左中
* 比较两次遍历的节点是否相同
* @param left
* @param right
* @return
*/
public boolean compare(TreeNode left,TreeNode right){
if(left == null && right == null) return true;
else if(left != null && right == null) return false;
else if(left == null && right != null) return false;
else if(left.val != right.val) return false;
boolean l = compare(left.left,right.right);
boolean r = compare(left.right,right.left);
boolean isSame = l && r;
return isSame;
}
public boolean isSymmetric2(TreeNode root) {
if (root == null) return true;
return compare(root.left,root.right);
}
104. 二叉树的最大深度
二叉树的层度除了层次遍历的方式之外,还有递归法和回溯法两种方式,代码如下
/**
* 递归解法
* @param root
* @return
*/
public int maxDepth2(TreeNode root){
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
/**
* 回溯解法:左右中的后续遍历方式
* @param root
* @return
*/
public static int result;
public void getDepth(TreeNode node , int depth){
result = depth > result ? depth : result;
if(node.left == null && node.right == null) return;
if(node.left != null){
depth ++; //深度+1
getDepth(node.left,depth); //往下走
depth --; //回溯 深度-1
}
if (node.right != null) {
depth ++; //深度+1
getDepth(node.right,depth); //往下走
depth --; //回溯 深度-1
}
return;
}
public int maxDepth3(TreeNode root) {
result = 0;
if(root == null) return result;
getDepth(root,1);
return result;
}
111. 二叉树的最小深度
写法可以模拟Code0104二叉树的最大深度,也是有三种写法
222. 完全二叉树的节点个数
首先我们要回忆完全二叉树的概念,只有可能是左右节点都为空,或者只有右节点为空的二叉树,满二叉树是特殊的完全二叉树
递归解法:想想递归求二叉树的最大深度
- 递归函数的返回值:int 参数:leftNode,rightNode
- 终止条件 : 左右节点都为空
- 套娃:调用自己
public int countNodes(TreeNode root) {
if(root == null)
return 0;
int leftNum = countNodes(root.left);
int rightNum = countNodes(root.right);
return leftNum + rightNum + 1;
}
迭代解法
随便一种遍历方式,遍历的过程记录节树
110. 平衡二叉树
首先了解什么是平衡二叉树,就是二叉树的左子树和右子树高度差的绝对值不超过一,同时子树的左子树和右子树也遵循这样的规定,这很容易让我们想到用递归的解法,代码如下
public int getHeight(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
if(root == null)
return 0;
int height = 0;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0; i<size; i++){
TreeNode node = queue.poll();
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
height ++;
}
return height;
}
public boolean isBalanced(TreeNode root) {
if(root == null)
return true;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
写了这么多,做个小结
- 对树的遍历方式,以及基于遍历的一些算法有了一定的了解
- 通过树对递归三部曲有了更加深刻的认识
- 初识回溯算法的魅力,回溯和递归本是不分家