代码随想录算法训练营第十四天|二叉树基础-二叉树迭代-二叉树

发布时间:2024年01月23日

二叉树基础

二叉树种类

满二叉树

在这里插入图片描述

完全二叉树

在这里插入图片描述

二叉搜索树

在这里插入图片描述

平衡二叉搜索树

在这里插入图片描述

二叉树的存储方式

链式存储

在这里插入图片描述

顺序存储

在这里插入图片描述

二叉树的遍历方式

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

  1. 深度优先遍历:先往深走,遇到叶子节点再往回走。
  2. 广度优先遍历:一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式,后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展,才有如下遍历方式:

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

二叉树的递归遍历

在这里插入图片描述

144.二叉树的前序遍历

前序遍历,中左右

代码:

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();//结果数组
        preorder(root,result);//开始从根节点遍历
        return result;
    }
    public void preorder(TreeNode root,List<Integer> res){
        if(root==null){
            return; //直接返回
        }
        res.add(root.val);//添加根节点
        preorder(root.left,res);
        preorder(root.right,res);
    }
}

145.二叉树的后序遍历

左右中

代码:

/**
 * 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> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postOrder(root,res);
        return res;
    }
    public void postOrder(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        postOrder(root.left,res);
        postOrder(root.right,res);
        res.add(root.val);
    }
}

94. 二叉树的中序遍历

左右中

代码

/**
 * 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 ArrayList<>();
        inOrder(root,res);
        return res;
    }
    public void inOrder(TreeNode root,List<Integer> res){
        if(root==null){
            return;
        }
        inOrder(root.left,res);
        res.add(root.val);
        inOrder(root.right,res);
    }
}

二叉树的迭代遍历

前序遍历(迭代法)-中左右->中右左(模拟出入栈)

我们先看一下前序遍历。

前序遍历是中左右,每次先处理的是中间节点,
那么先将根节点放入栈中
然后先将右孩子加入栈,再加入左孩子

为什么要先加入 右孩子,再加入左孩子呢? 因为这样出栈的时候才是中左右的顺序

动画如下:
在这里插入图片描述

代码

// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);//加入根节点
        while(!stack.isEmpty()){
            //中
            TreeNode node=stack.pop();//弹出根节点
            res.add(node.val);//储存根节点的数值
            //右
            if(node.right!=null){
                stack.push(node.right);
            }
            //左
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        return res;
    }
}

后序遍历(迭代法)

思路:

前序遍历的数组储存是中左右,那么把函数翻转,则变成数组储存是中右左,再将数组进行翻转,则变成左右中。
在这里插入图片描述

代码:

// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return res;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
        }
        Collections.reverse(res);//反转数组
        return res;
    }
}

中序遍历(迭代法)

为了解释清楚,我说明一下 刚刚在迭代的过程中,其实我们有两个操作:

  1. 处理:将元素放进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 (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;
    }
}

二叉树的统一迭代法-画图理解增加熟练

在这里插入图片描述

前序遍历写法-右左中(反过来)

/**
 * 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> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            TreeNode node=stack.peek();//栈中的第一个节点
            if(node!=null){
                stack.pop();//弹出避免重复,下面再将右左中节点添加到栈中
                if(node.right!=null){//添加右节点,空节点不入栈
                    stack.push(node.right); 
                }
                if(node.left!=null){//添加左节点,空节点不入栈
                    stack.push(node.left);
                }
                stack.push(node);//添加中节点
                stack.push(null);//中节点还没有处理,添加空节点null做标记
            }else{
                stack.pop();//弹出null
                node=stack.peek();//重新取出栈中元素
                stack.pop();//取出后再弹出
                res.add(node.val);
            }
        }
        return res;
    }
}

中序遍历写法-右中左

/**
 * 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;
 *     }
 * }
 */
/**
 * 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 ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null){//先放入根节点
            stack.push(root);
        }
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();//查找第一个结点
            if(node!=null){
                stack.pop();//弹出重复节点,按顺序放入右中左
                if(node.right!=null){
                    stack.push(node.right);
                }
                stack.push(node);
                stack.push(null);
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else{
                stack.pop();
                node = stack.peek();
                stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

后序遍历-中右左

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root!=null){//先放入根节点
            stack.push(root);
        }
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();//查找第一个结点
            if(node!=null){
                stack.pop();//弹出重复节点,按顺序放入中右左
                stack.push(node);
                stack.push(null);
                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
            }else{
                stack.pop();
                node = stack.peek();
                stack.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}
文章来源:https://blog.csdn.net/echoliuy/article/details/135765532
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。