欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树的定义 以及前中后序,层序遍历

程序员文章站 2022-06-28 16:21:27
class Solution { List list = new ArrayList<>(); public List preorderTraversal(TreeNode root) { if(root==null) return new ArrayList<>(); list.add(root.val); preorderTra.....

二叉树的定义 以及前中后序,层序遍历
二叉树的定义 以及前中后序,层序遍历

class Solution {
    List <Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null)
            return new ArrayList<>();
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
}
class Solution {
    List <Integer> list = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null)
            return list;
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }
}
class Solution {
    List <Integer> list = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return new ArrayList<Integer>();
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}

层序遍历:
层序遍历我认为也可以看作是树的广度优先搜索(BFS),以根节点开始,依次遍历一级邻接点,二级邻接点…等等
具体实现是用队列去实现
二叉树的定义 以及前中后序,层序遍历
力扣对于层序遍历的演示

class Solution {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return list;
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> innerList = new ArrayList<Integer>();;
            while(size--!=0){
                TreeNode treeNode = queue.poll();
                innerList.add(treeNode.val);
                if(treeNode.left != null)
                    queue.add(treeNode.left);
                if(treeNode.right != null)
                    queue.add(treeNode.right);
            }
            if(innerList != null)
                list.add(innerList);
        }
        return list;
    }
}

二叉树的定义 以及前中后序,层序遍历

二叉树的定义 以及前中后序,层序遍历

本文地址:https://blog.csdn.net/m0_45311187/article/details/110815326