拓冰网站定制 
一、二叉树的前序遍历给你二叉树的根节点 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 ListInteger res new ArrayList(); dfs(root, res); return res.stream() .mapToInt(Integer::intValue) .toArray(); } private void dfs(TreeNode root, ListInteger 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 ListInteger 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, ListInteger 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用于动态添加数据 ArrayListInteger resultList new ArrayList(); // 2.调用后序遍历递归函数 process(resultList, root); // 3.将ArrayList转换成int[]并返回 return listToArray(resultList); } // 后序遍历递归函数 public void process(ArrayListInteger resultList, TreeNode root) { if (root null) { return; } process(resultList, root.left); process(resultList, root.right); resultList.add(root.val); } // ArrayList转int[] public int[] listToArray(ArrayListInteger 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整型ArrayListArrayList */ public ArrayListArrayListInteger levelOrder (TreeNode root) { // write code here ArrayListArrayListInteger res new ArrayList(); if (root null) return res; DequeTreeNode queue new ArrayDeque(); queue.offer(root); while (!queue.isEmpty()) { ArrayListInteger 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整型ArrayListArrayList */ public ArrayListArrayListInteger Print (TreeNode pRoot) { // write code here ArrayListArrayListInteger res new ArrayListArrayListInteger(); if (pRoot null)return res; int j 0; ListTreeNode level new ArrayList(); ListTreeNode tmp new ArrayList(); level.add(pRoot); while (!level.isEmpty()) { ArrayListInteger 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; } }运行结果 二叉树（1）
一、二叉树的前序遍历给你二叉树的根节点 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 ListInteger res new ArrayList(); dfs(root, res); return res.stream() .mapToInt(Integer::intValue) .toArray(); } private void dfs(TreeNode root, ListInteger 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 ListInteger 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, ListInteger 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用于动态添加数据 ArrayListInteger resultList new ArrayList(); // 2.调用后序遍历递归函数 process(resultList, root); // 3.将ArrayList转换成int[]并返回 return listToArray(resultList); } // 后序遍历递归函数 public void process(ArrayListInteger resultList, TreeNode root) { if (root null) { return; } process(resultList, root.left); process(resultList, root.right); resultList.add(root.val); } // ArrayList转int[] public int[] listToArray(ArrayListInteger 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整型ArrayListArrayList */ public ArrayListArrayListInteger levelOrder (TreeNode root) { // write code here ArrayListArrayListInteger res new ArrayList(); if (root null) return res; DequeTreeNode queue new ArrayDeque(); queue.offer(root); while (!queue.isEmpty()) { ArrayListInteger 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整型ArrayListArrayList */ public ArrayListArrayListInteger Print (TreeNode pRoot) { // write code here ArrayListArrayListInteger res new ArrayListArrayListInteger(); if (pRoot null)return res; int j 0; ListTreeNode level new ArrayList(); ListTreeNode tmp new ArrayList(); level.add(pRoot); while (!level.isEmpty()) { ArrayListInteger 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; } }运行结果