二叉树理论基础

二叉树种类

满二叉树：每个非叶子节点都有且只有两个子节点。

和完全二叉树：除了最底层外，其他各层都是满的；最底层的节点都集中在左侧。

二叉搜索树：对于任意节点 u，左子树上所有节

点的值都小于 u.val，右子树上所有节点的值都大于 u.val。

平衡二叉树：任意节点的左右子树高度差 ≤ 1。

二叉树的存储方式

「二叉树可以链式存储，也可以顺序存储。」

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

遍历算法

1. 深度优先遍历（DFS）

   • 前序（Pre‑Order）：根 → 左 → 右

     /**
      * Definition for a binary tree node.
      * 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;
      *     }
      * }
      */
     class Solution {
         public List<Integer> inorderTraversal(TreeNode root) {
             List<Integer> res = new LinkedList<>();
             preorder(root, res);
             return res;
         }
         void preorder(TreeNode root,List<Integer> list){
                 if(root == null){
                     return;
                 }
                 list.add(root.val);
                 preorder(root.left,list);        
                 preorder(root.right,list);
             }
     }

   • 中序（In‑Order）：左 → 根 → 右

     
     class Solution {
         public List<Integer> inorderTraversal(TreeNode root) {
             List<Integer> res = new LinkedList<>();
             inorder(root, res);
             return res;
         }
         void inorder(TreeNode root,List<Integer> list){
                 if(root == null){
                     return;
                 }
                 inorder(root.left,list);
                 list.add(root.val);
                 inorder(root.right,list);
             }
     }

   • 后序（Post‑Order）：左 → 右 → 根

     
     class Solution {
         public List<Integer> inorderTraversal(TreeNode root) {
             List<Integer> res = new LinkedList<>();
             inorder(root, res);
             return res;
         }
         void inorder(TreeNode root,List<Integer> list){
                 if(root == null){
                     return;
                 }           
                 inorder(root.left,list);        
                 inorder(root.right,list);
                 list.add(root.val);
             }
     }

2. 广度优先遍历（BFS）/层序（Level‑Order）

   • 按层自上而下、同层从左到右依次访问，通常用队列实现。

 二叉树的定义

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

递归写法 

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以前序遍历为例：

1.首先，确认参数，因为我们访问的是节点，所以参数要包含节点对象，其次要返回访问的数值，所以也要包含一个list对象保存访问的值

2.每一层递归的终止条件就是遇见空节点，所以判断当前节点是否为空，为空就返回

3. 前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

迭代解决遍历

前序：因为迭代使用栈，而出栈顺序是先进后出，所以我们在遍历的时候要改变遍历的顺序，先遍历右节点，在遍历左节点，这时候就是左节点先出，符合根左右的习惯

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            TreeNode node = s.pop();
            list.add(node.val);
            if(node.right != null){
                s.push(node.right);
            }
            if(node.left != null){
                s.push(node.left);
            }
        }
        return list;
}}

中序：在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
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 (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return 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 node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

 层次遍历

思路：需要借助一个辅助队列来完成统计，即一层一层的入队