作者：敲代码の流川枫
博客主页：流川枫的博客
专栏：和我一起学java
语录：Stay hungry stay foolish
Apifox = Postman + Swagger + Mock + JMeter。集接口文档工具、接口Mock工具、接口自动化测试工具、接口调试工具于一体,提升 10 倍研发效率
1.三种遍历OJ
前序遍历
前序遍历按照根左右的访问规律进行遍历，我们这里定义一个list记录返回， 使用子问题的思想遍历
import java.util.ArrayList;
import java.util.List;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution{
public List<Integer> preoderTraversal(TreeNode root){
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
list.add(root.val);
List<Integer> leftTree = preoderTraversal(root.left);
list.addAll(leftTree);
List<Integer> rightTree = preoderTraversal(root.right);
list.addAll(rightTree);
return list;
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
List<Integer> lefttree = inorderTraversal(root.left);
list.addAll(lefttree);
list.add(root.val);
List<Integer> righttree = inorderTraversal(root.right);
list.addAll(righttree);
return list;
}
}
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
List<Integer> lefttree = postorderTraversal(root.left);
list.addAll(lefttree);
List<Integer> righttree = postorderTraversal(root.right);
list.addAll(righttree);
list.add(root.val);
return list;
}
}
获取树中节点的个数
还是在上次创建的二叉树中进行操作
方法一：遍历整个树
代码
public static int nodeSize = 0;
int size(TreeNode root){
if(root == null){
return 0;
}
nodeSize++;
size(root.left);
size(root.right);
return nodeSize;
}
测试
class Test{
public static void main(String[] args) {
TestBianryTree testBianryTree = new TestBianryTree();
TestBianryTree.TreeNode root = testBianryTree.creatTree();
testBianryTree.postOrde(root);
System.out.println();
System.out.println("==========");
int length = testBianryTree.size(root);
System.out.println(length);
}
}
方法二： 分解成子问题
节点个数 = 左子树总节点+右子树总节点+1
int size2(TreeNode root){
if(root == null){
return 0;
}
int leftsize = size2(root.left);
int rightsize = size2(root.right);
return leftsize+rightsize+1;
}
获取叶子节点的个数
方法一：分解为子问题
代码
int getLeafNodeCount(TreeNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right==null){
return 1;
}
int lefttree = getLeafNodeCount(root.left);
int righttree = getLeafNodeCount(root.right);
return lefttree+righttree;
}
测试
int count = testBianryTree.getLeafNodeCount(root);
System.out.println(count);
方法二：遍历
定义一个计数器，当节点的左右子树同时为空时，说明这是叶子节点
代码
public static int count = 0;
void getLeafNodeCount2(TreeNode root){
if(root == null){
return ;
}
if(root.left == null && root.right == null){
count++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
}
测试
System.out.println("==========");
testBianryTree.getLeafNodeCount2(root);
System.out.println(testBianryTree.count);
4.获取第K层节点的个数
相对于根节点的k层，就是根节点左树的K-1层+根节点右树的K-1层
代码
int getKLevelNodeCount(TreeNode root,int k){
if(root == null || k <= 0){
return 0;
}
if(k == 1){
return 1;
}
int tmp = getKLevelNodeCount(root.left,k-1)+
getKLevelNodeCount(root.right,k-1);
return tmp;
}
测试
int k = testBianryTree.getKLevelNodeCount(root,3);
System.out.println(k);
5.获取二叉树的高度
子问题的求解思路，求出左右子树的高度，相比较，返回最大的为树的高度
代码
int getHeight(TreeNode root){
if(root == null){
return 0;
}
int lefttree = getHeight(root.left);
int righttree = getHeight(root.right);
return lefttree > righttree ? lefttree + 1 : righttree + 1;
}
测试
System.out.println("============");
int height = testBianryTree.getHeight(root);
System.out.println("树的高度："+height);
注意不要将返回值写成这样：
return getHeight(root.left)>getHeight(root.right)
? getHeight(root.left)+1:getHeight(root.right)+1;
这样会出现重复递归的情况，测试用例较多时会运行超时
检测值为value的元素是否存在
先判断根节点的值是否是要找的值，然后再继续判断左右子树的值是否是要找的值
代码
TreeNode find(TreeNode root,int val){
if(root == null){
return null;
}
if(root.val == val){
return root;
}
TreeNode lefttree = find(root.left,val);
if(lefttree != null){
return lefttree;
}
TreeNode righttree = find(root.right,val);
if(righttree != null){
return righttree;
}
return null;
}
测试
System.out.println("===========");
TestBianryTree.TreeNode treeNode = testBianryTree.find(root,'A');
System.out.println(treeNode.val);
" 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！
原文链接: https://blog.csdn.net/chenchenchencl/article/details/127171607