第一题：二叉树的前序遍历
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例1：
示例
输入：{1,#,2,3}
返回值：[1,2,3]
题解
import java.util.*; public class Solution { public void preorder(List<Integer> list, TreeNode root){ //遇到空节点则返回 if(root == null) return; //先遍历根节点 list.add(root.val); //再去左子树 preorder(list, root.left); //最后去右子树 preorder(list, root.right); } public int[] preorderTraversal (TreeNode root) { //添加遍历结果的数组 List<Integer> list = new ArrayList(); //递归前序遍历 preorder(list, root); //返回的结果 int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++) res[i] = list.get(i); return res; } }
第二题：二叉树的中序遍历
题目描述
给定一个二叉树的根节点root，返回它的中序遍历结果。
进阶：空间复杂度 O(n)，时间复杂度 O(n)
示例
示例1
输入：{1,2,#,#,3}
返回值：[2,3,1]
示例2
输入：{}
返回值：[]
示例3
输入：{1,2}
返回值：[2,1]
示例4
输入：{1,#,2}
返回值：[1,2]
备注：
树中节点数目在范围 [0, 100] 内
树中的节点的值在[-100,100]以内
题解
import java.util.*; public class Solution { public void inorder(List<Integer> list, TreeNode root){ //遇到空节点则返回 if(root == null) return; //先去左子树 inorder(list, root.left); //再访问根节点 list.add(root.val); //最后去右子树 inorder(list, root.right); } public int[] inorderTraversal (TreeNode root) { //添加遍历结果的数组 List<Integer> list = new ArrayList(); //递归中序遍历 inorder(list, root); //返回的结果 int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++) res[i] = list.get(i); return res; } }
第三题：二叉树的后序遍历
题目描述
给定一个二叉树，返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
样例图：
示例
示例1
输入：{1,#,2,3}
返回值：[3,2,1]
说明：如题面图
示例2
输入：{1}
返回值：[1]
题解
import java.util.*; public class Solution { public void postorder(List<Integer> list, TreeNode root){ //遇到空节点则返回 if(root == null) return; //先去左子树 postorder(list, root.left); //再去右子树 postorder(list, root.right); //最后访问根节点 list.add(root.val); } public int[] postorderTraversal (TreeNode root) { //添加遍历结果的数组 List<Integer> list = new ArrayList(); //递归后序遍历 postorder(list, root); //返回的结果 int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++) res[i] = list.get(i); return res; } }
第四题：求二叉树的层序遍历
描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
提示:
0 <= 二叉树的结点数 <= 1500
示例
示例1
输入：{1,2}
返回值：[[1],[2]]
示例2
输入：{1,2,3,4,#,#,5}
返回值：[[1],[2,3],[4,5]]
题解
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ //前序遍历模板； void f(TreeNode* root,int level,vector<vector<int>> &res){ if(!root)return ; if(level>=res.size()){//最新的深度，申请一个数组存储； res.push_back(vector<int> {}); } res[level].push_back(root->val); f(root->left,level+1,res);//遍历左子树; f(root->right,level+1,res);//遍历右子树； } vector<vector<int> > levelOrder(TreeNode* root) { // write code here vector<vector<int>> res;//存储最终结果； f(root,0,res);//前序遍历； return res;//返回结果； } };
第五题：二叉树的最大深度
题目描述
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）
要求： 空间复杂度 O(1),时间复杂度 O(n)
示例1
输入：{1,2}
返回值：2
示例2
输入：{1,2,3,4,#,#,5}
返回值：3
题解
import java.util.*; public class Solution { public int maxDepth (TreeNode root) { //空节点没有深度 if(root == null) return 0; //返回子树深度+1 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } }
