随想录日记part12

$time：$ 2024.03.05

---

---

主要内容：今天的主要内容是了解二叉树的理论基础，并且熟练掌握如何递归和迭代遍历二叉树。

• 理论基础
• 递归遍历
• 迭代遍历
• 统一迭代

---

---

Topic1二叉树理论基础

1.二叉树的题目分类：

2.二叉树的分类:

2.1 满二叉树：

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

2.2 完全二叉树：

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

2.3 二叉搜索树：

叉搜索树是有数值的，二叉搜索树是一个有序树

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 它的左、右子树也分别为二叉排序树

2.4 平衡二叉搜索树(AVL树)：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。如图：
$C++$ 中 $map、set、multimap，multiset$ 的底层实现都是平衡二叉搜索树，$map、set$ 的增删操作时间复杂度是 $logn$，注意 $unordered\_map$、$unordered\_set$ 底层实现是哈希表。

2.5 二叉树存储方式：

二叉树可以链式存储，也可以顺序存储。
链式存储如图：

顺序存储的方式如图：

用数组来存储二叉树如何遍历的呢
如果父节点的数组下标是 $i$，那么它的左孩子就是 $i\ast 2+1$，右孩子就是 $i\ast 2+2$。

2.6二叉树的遍历方式：

二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，遇到叶子节点再往回走。
• 广度优先遍历：一层一层的去遍历。

2.6.1 深度优先遍历:

• 前序遍历（递归法，迭代法）
• 中序遍历（递归法，迭代法）
• 后序遍历（递归法，迭代法）
  

2.6.2 广度优先遍历:

• 层次遍历（迭代法）

2.7二叉树的节点定义：

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;
    }
}

---

---

Topic2二叉树的递归遍历

规则总结：

• 1.确定递归函数的参数和返回值：
• 2.确定终止条件
• 3.确定单层递归的逻辑

java实现的代码如下：

class Solution {//递归前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> tem=new ArrayList<Integer>();
        Traversal(root,tem);
        return tem;
    }
    void Traversal(TreeNode root,List<Integer> result){
        if(root==null)return;
        result.add(root.val);//中
        Traversal(root.left,result);//左
        Traversal(root.right,result);//右
    }
}
class Solution {//递归中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> tem=new ArrayList<Integer>();
        Traversal(root,tem);
        return tem;
    }
    void Traversal(TreeNode root,List<Integer> result){
        if(root==null)return;
        Traversal(root.left,result);//左
        result.add(root.val);//中
        Traversal(root.right,result);//右
    }
}

class Solution {//递归后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> tem=new ArrayList<Integer>();
        Traversal(root,tem);
        return tem;
    }
    void Traversal(TreeNode root,List<Integer> result){
        if(root==null)return;
        Traversal(root.left,result);//左
        Traversal(root.right,result);//右
        result.add(root.val);//中
    }
}

---

---

Topic3二叉树的迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。用栈也可以是实现二叉树的前后中序遍历。

• 1.前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。动画如下：

class Solution {// 递归前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            result.add(tem.val);//中
            if (tem.right != null)//右孩子入栈
                stack.push(tem.right);
            if (tem.left != null)//左孩子入栈
                stack.push(tem.left);
        }
        return result;
    }

---

• 2.中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点(也就是在把节点的数值放进 $result$ 数组中)，这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。动画如下：

class Solution {// 递归中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }else{
                cur=stack.pop();
                result.add(cur.val);
                cur=cur.right;
            }
        }
        return result;
    }

---

• 3.后序遍历只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转 $result$ 数组，输出的结果顺序就是左右中了，如下图：

class Solution {// 递归后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tem = stack.pop();
            result.add(tem.val);//中
            if (tem.left != null)//左孩子入栈
                stack.push(tem.left); 
            if (tem.right != null)//右孩子入栈
                stack.push(tem.right);
        }
        Collections.reverse(result);
        return result;
    }
}

---

---

Topic4二叉树的统一迭代法

三种遍历方式，使用迭代法是可以写出统一风格的代码，统一写法如下：

上面的方法无法解决同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记：就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。
详细看如下代码：

class Solution {//先序
   public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> result = new LinkedList<>();
       Stack<TreeNode> st = new Stack<>();
       if (root != null) st.push(root);
       while (!st.empty()) {
           TreeNode node = st.peek();
           if (node != null) {
               st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
               if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
               if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
               st.push(node);                          // 添加中节点
               st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
               
           } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
               st.pop();           // 将空节点弹出
               node = st.peek();    // 重新取出栈中元素
               st.pop();
               result.add(node.val); // 加入到结果集
           }
       }
       return result;
   }
}

class Solution {//中序
public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> result = new LinkedList<>();
   Stack<TreeNode> st = new Stack<>();
   if (root != null) st.push(root);
   while (!st.empty()) {
       TreeNode node = st.peek();
       if (node != null) {
           st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
           if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
           st.push(node);                          // 添加中节点
           st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

           if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
       } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
           st.pop();           // 将空节点弹出
           node = st.peek();    // 重新取出栈中元素
           st.pop();
           result.add(node.val); // 加入到结果集
       }
   }
   return result;
}
}

class Solution {//后序
  public List<Integer> postorderTraversal(TreeNode root) {
       List<Integer> result = new LinkedList<>();
       Stack<TreeNode> st = new Stack<>();
       if (root != null) st.push(root);
       while (!st.empty()) {
           TreeNode node = st.peek();
           if (node != null) {
               st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
               st.push(node);                          // 添加中节点
               st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
               if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
               if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
                              
           } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
               st.pop();           // 将空节点弹出
               node = st.peek();    // 重新取出栈中元素
               st.pop();
               result.add(node.val); // 加入到结果集
           }
       }
       return result;
  }
}