企业官网建设流程全解析

一、二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序遍历。

数据范围：二叉树的节点数量满足 1≤n≤100 ，二叉树节点的值满足 1≤val≤100 ，树的各节点的值各不相同

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { public int[] preorderTraversal (TreeNode root) { // write code here List<Integer> res = new ArrayList<>(); dfs(root, res); return res.stream() .mapToInt(Integer::intValue) .toArray(); } private void dfs(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val); dfs(root.left, res); dfs(root.right, res); } }

运行结果

二、二叉树的中序遍历

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足 0≤n≤1000，树上每个节点的值满足 −1000≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] inorderTraversal (TreeNode root) { // write code here List<Integer> list = new ArrayList(); travelsal(root, list); int[] num = new int[list.size()]; for (int i = 0; i < list.size(); i++) { num[i] = list.get(i); } return num; } public void travelsal(TreeNode root, List<Integer> list) { if (root == null) { return; } if (root.left != null) { travelsal(root.left, list); } list.add(root.val); if (root.right != null) { travelsal(root.right, list); } } }

运行结果

三、二叉树的后序遍历

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足 1≤n≤100，二叉树节点的值满足 1≤val≤100，树的各节点的值各不相同

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] postorderTraversal (TreeNode root) { // write code here // 1.初始化一个ArrayList用于动态添加数据 ArrayList<Integer> resultList = new ArrayList<>(); // 2.调用后序遍历递归函数 process(resultList, root); // 3.将ArrayList转换成int[]并返回 return listToArray(resultList); } // 后序遍历递归函数 public void process(ArrayList<Integer> resultList, TreeNode root) { if (root == null) { return; } process(resultList, root.left); process(resultList, root.right); resultList.add(root.val); } // ArrayList转int[] public int[] listToArray(ArrayList<Integer> resultList) { int[] resultArray = new int[resultList.size()]; for (int i = 0; i < resultArray.length; i++) { resultArray[i] = resultList.get(i); } return resultArray; } }

运行结果

四、求二叉树的层序遍历

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { // write code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if (root == null) return res; Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { ArrayList<Integer> curLevelRes = new ArrayList<>(); // 当前层要遍历的节点数量 int n = queue.size(); for (int i = 0; i < n; i++) { TreeNode cur = queue.poll(); curLevelRes.add(cur.val); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } res.add(curLevelRes); } return res; } }

运行结果

五、按之字形顺序打印二叉树

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0≤n≤1500,树上每个节点的val满足 ∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pRoot TreeNode类 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) { // write code here ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if (pRoot == null)return res; int j = 0; List<TreeNode> level = new ArrayList<>(); List<TreeNode> tmp = new ArrayList<>(); level.add(pRoot); while (!level.isEmpty()) { ArrayList<Integer> levelval = new ArrayList<>(); for (TreeNode node : level) { if (node == null) continue; levelval.add(node.val); } Collections.reverse(level); for (TreeNode node : level) { if (j % 2 == 0) { if (node.right != null)tmp.add(node.right); if (node.left != null)tmp.add(node.left); } else { if (node.left != null)tmp.add(node.left); if (node.right != null)tmp.add(node.right); } } res.add(levelval); level.clear(); level.addAll(tmp); tmp.clear(); j++; } return res; } }

运行结果

六、二叉树的最大深度

求给定二叉树的最大深度，

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）

数据范围：0≤n≤100000，树上每个节点的val满足 ∣val∣≤100
要求： 空间复杂度 O(1),时间复杂度 O(n)

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { if(root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left,right)+1; } }

运行结果