树的基础知识和遍历实现(JAVA)

简介: 树的基础知识和遍历实现(JAVA)

概念:

1.树的遍历分为前序遍历、中序遍历、后序遍历
2.前中后,其实总结来说,就是指根节点的先后遍历顺序
1)前序遍历:先遍历根节点,然后是左子树,最后是右子树
2)中序遍历:先遍历左子树,然后是根节点,最后是右子树
3)后序遍历:先遍历左子树,然后是右子树,最后是根节点
3.遍历的方式分为递归实现、迭代实现、层序实现
层序遍历就是逐层遍历树结构
广度优先搜索是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。 该算法从一个根节点开始,首先访问节点本身。 然后遍历它的相邻节点,其次遍历它的二级邻节点、三级邻节点,以此类推
通常,我们使用一个叫做队列的数据结构来帮助我们做广度优先搜索

遍历的实现:

1.递归实现

1)前序遍历

class Solution {
    /**
     * 递归前序遍历
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preOrder(root, result);
        return result;
    }

    private void preOrder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preOrder(root.left, result);
        preOrder(root.right, result);
    }
}
AI 代码解读

2)中序遍历

class Solution {
    /**
     * 递归中序遍历
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        inOrder(root, result);
        return result;
    }

    private void inOrder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inOrder(root.left, result);
        result.add(root.val);
        inOrder(root.right, result);
    }
}
AI 代码解读

3)后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        postOrder(root, result);
        return result;
    }

    private void postOrder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        postOrder(root.left, result);
        postOrder(root.right, result);
        result.add(root.val);
    }
}
AI 代码解读

2.迭代实现

1)前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                result.add(root.val);
                root = root.left;
            }

            if (!stack.isEmpty()) {
                root = stack.pop();
                root = root.right;
            }
        }
        return result;
    }
}
AI 代码解读

2)中序遍历

class Solution {
   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            if (!stack.isEmpty()) {
                root = stack.pop();
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }
}
AI 代码解读

3)后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                result.addFirst(root.val);
                root = root.right;
            }

            if (!stack.isEmpty()) {
                root = stack.pop();
                root = root.left;
            }
        }
        return result;
    }
}
AI 代码解读

3.层序实现

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 二叉树的层序遍历,使用队列的特性,把每一层元素入队,然后进行按序出队的同时,将每个元素的左右节点入队,直到队列为null
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 用于存储每层元素
            List<Integer> levelValues = new ArrayList<>();
            int size = queue.size();
            // 把每一层元素入队,然后进行按序出队的同时,将每个元素的左右节点入队
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelValues.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 将遍历到本层元素,加入到结果链表中
            result.add(levelValues);
        }
        return result;
    }
}
AI 代码解读
目录
打赏
0
0
0
0
30
分享
相关文章
|
4月前
|
《从头开始学java,一天一个知识点》之:数组入门:一维数组的定义与遍历
**你是否也经历过这些崩溃瞬间?** - 看了三天教程,连`i++`和`++i`的区别都说不清 - 面试时被追问&quot;`a==b`和`equals()`的区别&quot;,大脑突然空白 - 写出的代码总是莫名报NPE,却不知道问题出在哪个运算符 这个系列就是为你打造的Java「速效救心丸」!我们承诺:每天1分钟,地铁通勤、午休间隙即可完成学习;直击痛点,只讲高频考点和实际开发中的「坑位」;拒绝臃肿,没有冗长概念堆砌,每篇都有可运行的代码标本。明日预告:《多维数组与常见操作》。 通过实例讲解数组的核心认知、趣味场景应用、企业级开发规范及优化技巧,帮助你快速掌握Java数组的精髓。
92 23
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
196 3
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
108 1
|
9月前
|
Java一分钟之-数组的创建与遍历
数组作为Java中存储和操作一组相同类型数据的基本结构,其创建和遍历是编程基础中的基础。通过不同的创建方式,可以根据实际需求灵活地初始化数组。而选择合适的遍历方法,则可以提高代码的可读性和效率。掌握这些基本技能,对于深入学习Java乃至其他编程语言的数据结构和算法都是至关重要的。
69 6
java遍历hdfs路径信息,报错EOFException
java遍历hdfs路径信息,报错EOFException
98 3
|
11月前
|
|
11月前
|
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
210 1
Java遍历Map集合的方法
在Java中,遍历Map集合主要有四种方式:1) 使用`keySet()`遍历keys并用`get()`获取values;2) 使用`entrySet()`直接遍历键值对,效率较高;3) 通过`Iterator`遍历,适合在遍历中删除元素;4) Java 8及以上版本可用`forEach`和Lambda表达式,简洁易读。`entrySet()`通常性能最佳,而遍历方式的选择应考虑代码可读性和数据量。
154 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问