1. Toy模板网首页
  2. > Toy博客

二叉树相关算法需了解汇总-基础算法操作

7月前 作者：糖果店的幽灵 分类：Toy博客 阅读(28) 违法举报

这篇具有很好参考价值的文章主要介绍了二叉树相关算法需了解汇总-基础算法操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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<>();
        traversal(res,root);
        return res;
    }

    public void traversal(List<Integer> list, TreeNode root){
        if(root == null){
            return;
        }
        traversal(list,root.left);
        traversal(list,root.right);
        list.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<>();
        traversal(res,root);
        return res;
    }   
    public void traversal(List<Integer> list,TreeNode root){
        if(root == null){
            return;
        }

        traversal(list,root.left);
        list.add(root.val);
        traversal(list,root.right);
    }
}

102.二叉树的层序遍历

/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(res,root,0);
        return res;
    }

    public void traversal(List<List<Integer>> list,TreeNode root, int deep){
        if(root == null){
            return;
        }
        if(list.size() < deep+1){
            list.add(new ArrayList<>());
        }

        list.get(deep).add(root.val);
        traversal(list,root.left,deep+1);
        traversal(list,root.right,deep+1);
    }
}

107.二叉树的层次遍历倒序

/**
 * 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<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(res,root,0);
        Collections.reverse(res);
        return res;
    }

    public void traversal(List<List<Integer>> list,TreeNode root,int deep){
        if(root == null){
            return;
        }

        if(list.size() < deep+1){
            list.add(new ArrayList<>());
        }

        list.get(deep).add(root.val);
        traversal(list,root.left,deep+1);
        traversal(list,root.right,deep+1);
    }
}

199.二叉树的右视图

/**
 * 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> rightSideView(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(res,root,0);
        List<Integer> result = new ArrayList<>();
        for(List<Integer> list:res){
            result.add(list.getLast());
        }

        return result;

    }

    public void traversal(List<List<Integer>> list,TreeNode root,int deep){
        if(root == null){
            return;
        }

        while(list.size() <deep+1){
            list.add(new ArrayList<>());
        }

        list.get(deep).add(root.val);
        traversal(list,root.left,deep+1);
        traversal(list,root.right,deep+1);
    }
}

637.二叉树的层平均值

/**
 * 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<Double> averageOfLevels(TreeNode root) {

        List<List<Integer>> rest = new ArrayList<>();
        List<Double> res = new ArrayList<>();
        traversal(rest,root,0);
 
        for(List<Integer> l :rest){
            res.add(l.stream()
                    .mapToInt(Integer::intValue)
                    .average()
                    .orElse(0));
        }
        return res;
    }

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

429.N叉树的层序遍历


/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(res,root,0);
        return res;
    }

    public void traversal(List<List<Integer>> list,Node root,int deep){
        if(root == null){
            return;
        }

        if(list.size() < deep+1){
            list.add(new ArrayList<>());
        }
        list.get(deep).add(root.val);

        for(Node node : root.children){
            traversal(list,node,deep+1);
        }
        
    }
}

515.在每个树行中找最大值

/**
 * 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> largestValues(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(res,root,0);
        List<Integer> result = new ArrayList<>();

        for(List<Integer> l : res){
            result.add(l.stream().max(Integer::compare).orElse(0));
        }

        return result;
    }

    public void traversal(List<List<Integer>> list, TreeNode root, int deep){
        if(root == null){
            return;
        }
        if(list.size() < deep+1){
            list.add(new ArrayList<>());
        }

        list.get(deep).add(root.val);
        traversal(list,root.left,deep+1);
        traversal(list,root.right,deep+1);
    }
}

116.填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return root;
        }

        Queue<Node> nodeq = new LinkedList<>();
        nodeq.add(root);
        while(!nodeq.isEmpty()){
            int size = nodeq.size();

            for(int i = 0; i < size; i++){
                Node node = nodeq.poll();
                if(i < size - 1){
                    node.next = nodeq.peek();
                }

                if(node.left != null){
                    nodeq.add(node.left);
                }

                if(node.right != null){
                    nodeq.add(node.right);
                }
            }
        }

        return root;
    }

}

104.二叉树的最大深度

/**
 * 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 int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return Math.max(leftH,rightH) + 1;

    }
}

111.二叉树的最小深度

/**
 * 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 int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        int leftH = minDepth(root.left);
        int rightH = minDepth(root.right);
        if(leftH == 0 || rightH == 0){
            return Math.max(leftH,rightH) + 1;
        }
        return Math.min(leftH,rightH)+ 1;
    }
}

文章来源地址https://www.toymoban.com/news/detail-836812.html

到了这里，关于二叉树相关算法需了解汇总-基础算法操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 算法刷题Day 17 平衡二叉树+二叉树的所有路径+左叶子之和

    计算左右两棵子树的高度，如果有一个高度是-1（有一棵子树不平衡），直接返回-1，否则计算高度差，判断是否不平衡 使用 回溯 的方法，每次处理一个节点之前要把它push进table里，处理完之后又要把它pop出来 处理一个节点时，要判断它是否是左节点（需要父节点，可以通

    2024年02月15日
    浏览(31)
  • 二叉树的相关操作

    二叉树的相关操作

    本文的数据结构基于C语言练习。 C语言中的二叉树是一种数据结构，用于表示具有层次关系的数据集合。它由一个根节点开始，每个节点最多有两个子节点，分别称为左子节点和右子节点。 二叉树有许多相关性质，其中一些重要的包括： 深度：指从根节点到某个节点的路径

    2024年02月08日
    浏览(19)

  • 算法刷题Day 20 最大二叉树+合并二叉树+二叉搜索树中的搜索+验证二叉搜索树

    递归 递归 迭代 递归 迭代 遇到两个坑的地方： 递归的时候，不能光验证左子树的根节点小于当前根节点，右子树的根节点大于但当前根节点，别忘了左子树上的每一个节点都要求比根节点要小，右子树上的每一个节点都要求比根节点大。 根节点跟左（右）子树中的某一个节

    2024年02月16日
    浏览(31)
  • 二叉树相关算法

    二叉树相关算法

    二叉树的定义就不在这里多说了，下面这个图就是一个简单的二叉树： 二叉树的三种遍历方式： 前序遍历：头左右，也就是先头后左再右：1245367 中序遍历：左头右，也就是先左后头再右：4251637 后序遍历：左头右，也就是先左后右再头：4526731 测试代码： 那么我们可以看出

    2024年02月07日
    浏览(20)

  • 算法-二叉树相关

    判断二叉树是否是完全二叉树 思路：层次遍历，如果之前某个节点叶子节点为空，队列后续的所有节点的左右节点都不能非空，并且如果节点左节点为null但是右节点不为null该二叉树一定不是满二叉树 思路2：使用递归方式，返回以当前节点为头结点的二叉树是否是满二叉树

    2024年02月21日
    浏览(22)

  • 算法刷题Day 16 二叉树的最大深度+N叉树的最大深度+二叉树的最小深度+完全二叉树的节点个数

    递归法 迭代法 使用层序的方法，相对比较好理解 递归法 迭代法 跟二叉树的迭代差不多意思。 要想到是后序遍历 递归法 先计算左右两棵子树的节点数，再加和，用后序遍历的方法 迭代法 迭代法用层序遍历来处理 适用于完全二叉树的优化 完全二叉树优化方法没自己想出来

    2024年02月17日
    浏览(32)

  • 算法刷题Day 37 单调递增的数字+监听二叉树

    两个可能经常要用到的函数 字符串转数字： to_string() 数字转字符串： stoi() 利用树后续遍历，同时加上状态转移的方法，非常值得反复学习

    2024年02月13日
    浏览(26)
  • 二叉树相关操作---纯代码实现详解

    二叉树相关操作---纯代码实现详解

    目录 前言 (很重要) 二叉树的概念 二叉树的相关术语 相关操作菜单   二叉树的构造  创建二叉树 先序遍历二叉树    中序遍历二叉树  后序遍历二叉树  层次遍历二叉树  二叉树的深度  二叉树的叶子结点数  二叉树的结点数 整体代码 结果展示 结束语         大家好，

    2023年04月09日
    浏览(21)
  • 数据结构：二叉树及相关操作

    数据结构：二叉树及相关操作

    在实现二叉树前，我们要先对树产生一些基本的认识，才可以去实现它。树的用途非常广泛，向文件系统的目录树结构等。 树是一种 非线性的数据结构 ，它是由n（n=0）个有限结点组成一个具有层次关系的集合。 有一个特殊的结点，称为根结点，根节点没有前驱结点。 除根

    2024年02月11日
    浏览(33)

  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目： 654. 最大二叉树 解析： 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目： 617.合并二叉树 解析： 代码随想录解析 解题思路 如果都为root1, root2都为空，返回null；如果root1为空，root2不为空，返回root2；如果roo1不为空，root2为空，返回root

    2024年04月10日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包