二叉树 - 二叉树基础以及遍历 - 《LeetCode题目总结》

1、理论基础
- 1.1 二叉树的种类
- 1.2 二叉树的存储方式
  - 链式存储
  - 数组存储
2、二叉树的遍历
- 2.1 深度优先遍历
- 2.2 广度优先遍历
  - 2.2.1 层次遍历
3、二叉树的高度与深度

1、理论基础

1.1 二叉树的种类

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树

平衡二叉树

又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

1.2 二叉树的存储方式

链式存储

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

数组存储

如果父节点的数组下标是 i，那么它的左孩子就是 i 2 + 1，右孩子就是 i 2 + 2。

2、二叉树的遍历

2.1 深度优先遍历

2.1.1 前序遍历

递归

确定递归函数的参数和返回值
确定终止条件

确定单层递归的逻辑

void preorderTraversal(TreeNode root, List<Integer> list){
   if ( root == null )
       return ;
   list.add(root.val);
   preorderTraversal(root.left, list);
   preorderTraversal(root.right, list);
}

迭代

迭代树时，要分清访问顺序，和处理顺序，例如中序遍历的时候访问到了根节点，但是不处理它（不加入结果），访问到左叶子结点才处理叶子结点
前序遍历是中左右，处理顺序也是中左右，每次先处理的是中间节点，那么入栈顺序就应该是中右左，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子
后序遍历是左右中，反转一下是中右左，现在只要把前序遍历的左右子结点入栈顺序改一下，就可以，得到的结果再反转回去即可

中序遍历是左中右，访问顺序确实中左右，访问顺序和处理顺序不一致

List<Integer> preorderTraversal(TreeNode root){
   List<Integer> result = new ArrayList<>();
   if (root == null)
       return result;
   ArrayDeque<TreeNode> stack = new ArrayDeque<>();
   stack.addLast(root);
   while ( !stack.isEmpty() ){
        TreeNode node = stack.pollLast();
        result.add(node.val);
        if (node.right != null){
            stack.addLast(node.right);
        }
        if (node.left != null){
            stack.addLast(node.left);
        }
   }
   return result;
}

2.1.2 中序遍历

void inorderTraversal(TreeNode root, List<Integer> list){
   if ( root == null )
       return;
   inorderTraversal(root.left, list);
   list.add(root.val);
   inorderTraversal(root.right, list);
}

List<Integer> inorderTraversal(TreeNode root){
   List<Integer> result = new ArrayList<>();
   if (root == null)
       return res;
   ArrayDeque<TreeNode> stack = new ArrayDeque<>();
   TreeNode cur = root; //定义一个指针用来访问节点
   //这里不是立刻添加root结点到栈中
   //因为没有立刻添加，所以栈一开始可能是空的，得加个条件进循环
   while ( cur!=null || !stack.isEmpty()){ //当指针为空或者栈为空时结束循环
       if ( cur!=null ){ //没有访问到叶子结点
           stack.addLast(cur);
           cur = cur.left;
       }else{
           cur = stack.pollLast();//当cur为空时，左边访问到底了，弹出元素即为左叶子结点
           result.add(cur.val);
           cur = cur.right;//访问右子树
       }
   }
   return result;
}

2.1.3 后序遍历

void postorderTraversal(TreeNode root, List<Integer> list){
   if ( root == null )
       return;
   postorderTraversal(root.left, list);
   postorderTraversal(root.right, list);
   list.add(root.val);
}

List<Integer> postorderTraversal(TreeNode root){
   List<Integer> result = new ArrayList<>();
   if (root == null)
       return result;
   ArrayDeque<TreeNode> stack = new ArrayDeque<>();
   stack.addLast(root);
   while (!stack.isEmpty()){
       TreeNode node = stack.pollLast();
       result.add(node.val);
       if (node.left!=null)
           stack.addLast(node.left);
       if (node.right!=null)
           stack.addLast(node.right);
   }
   Collections.reverse(result);
   return result;
}

2.2 广度优先遍历

2.2.1 层次遍历

递归

  public List<List<Integer>> resList = new ArrayList<>(); 
  void levelOrderTraversal(TreeNode root, Integer deep){
      if (root == null)
          return;
      deep++;
      if (resList.size() < deep){
          List<Integer> item = new ArrayList<>();
          resList.add(item);
      }
      resList.get(deep-1).add(root.val);
      levelOrderTraversal(root.left,deep);
      levelOrderTraversal(root.right,deep);
  }

迭代

  public List<List<Integer>> resList = new ArrayList<>();
  void levelOrderTraversal(TreeNode root){
      if (root == null) 
          return;
      ArrayDeque<TreeNode> queue = new ArrayDeque<>();
      queue.addLast(root);
      while (!queue.isEmpty()){
          List<Integer> item = new ArrayList<>();
          int len = queue.size();
          while ( len > 0 ){ //这里不能直接用queue.size()，因为queue长度在不断变化
              TreeNode node = queue.pollFirst();
              item.add(node.val);
              if (node.left!=null)
                  queue.addLast(node.left);
              if (node.right!=null)
                  queue.addLast(node.right);
              len--;
          }
          resList.add(item);
      }
  }

3、二叉树的高度与深度

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：

因为求深度可以从上到下去查所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）