算法训练营Day14(二叉树)

2023-12-13 03:55:51

理论基础

这里的话,学的也不少,就是注意一下java中容器的支持吧,hashMap这里,jdk8以后是hash表

数组+链表转红黑树的方式,这里的话采用的红黑树是完全二叉树的一种

另外优先级队列PriorityQueue是一个二叉堆,也是完全二叉树的一种。

二叉树的遍历方式:广度优先:层序遍历

深度优先:前中后

另外还有递归遍历非递归遍历(叫做 迭代法)【因为递归的本质也是栈

TreeMap这里好就是单纯的二叉树,红黑树,不涉及哈希表

可以看下这篇文章

http://t.csdnimg.cn/Nq3ZY

递归遍历

递归

递归需要注意的地方:

1、参数和返回值

? ? ? ? 可动态调整~

? ? ? ? 二叉树一般是(根节点,数组)

2、结束条件

? ? ? ? 二叉树终止条件是指针为null的时候

3、确认递归的逻辑

? ? ? ? 处理的逻辑就是,往数组放元素。

前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root,res);
        return res;
    }
    private void preorder(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
    }
}

中序遍历

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root,res);
        return res;
    }
    private void inorder(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        inorder(root.left,result);
        result.add(root.val);
        inorder(root.right,result);
    }

后序遍历

145. 二叉树的后序遍历 - 力扣(LeetCode)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root,res);
        return res;
    }
    private void preorder(TreeNode root,List<Integer> result){
        if(root==null){
            return;
        }
        preorder(root.left,result);
        preorder(root.right,result);
        result.add(root.val);
    }
}

日后补充(我基础不好~hh)

迭代遍历?(基础不好的录友,迭代法可以放过)

题目链接/文章讲解/视频讲解:代码随想录

?统一迭代???(基础不好的录友,迭代法可以放过)

这是统一迭代法的写法,?如果学有余力,可以掌握一下

题目链接/文章讲解:代码随想录

文章来源:https://blog.csdn.net/weixin_65728526/article/details/134946546
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。