[数据结构与算法]LeetCode:树相关算法小结

树

这段时间刷了数据结构中”树“的算法，刷了有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);
 ?  }

写了这么多，做个小结

• 对树的遍历方式，以及基于遍历的一些算法有了一定的了解

• 通过树对递归三部曲有了更加深刻的认识

• 初识回溯算法的魅力，回溯和递归本是不分家