树
这段时间刷了数据结构中”树“的算法，刷了有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. 完全二叉树的节点个数
首先我们要回忆完全二叉树的概念，只有可能是左右节点都为空，或者只有右节点为空的二叉树，满二叉树是特殊的完全二叉树
递归解法：想想递归求二叉树的最大深度
? 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);
? }
写了这么多，做个小结
|