Java数据结构——二叉树的基本操作

喜欢ヅ旅行 2023-10-10 15:07 39阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> [Apifox = Postman + Swagger + Mock + JMeter。集接口文档工具、接口Mock工具、接口自动化测试工具、接口调试工具于一体,提升 10 倍研发效率][Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]

1.三种遍历OJ

前序遍历

中序遍历

后序遍历

2. 获取树中节点的个数

3. 获取叶子节点的个数

4.获取第K层节点的个数

5.获取二叉树的高度

6. 检测值为value的元素是否存在

--------------------

## 1.三种遍历OJ ##

### [前序遍历][Link 2] ###

前序遍历按照根左右的访问规律进行遍历，我们这里定义一个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;
        }
    
    }

### [中序遍历][Link 3] ###

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;
    
        }
    }

### [后序遍历][Link 4] ###

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;
        }
    }

## 2. 获取树中节点的个数 ##

> ![25cc011b47c142578bf41a86db779d6d.png][]
> 
> 还是在上次创建的二叉树中进行操作

方法一：遍历整个树

代码

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);
        }
    }

![464848b3b765441a9096fb30a88d97e3.png][]

方法二： 分解成子问题

节点个数 = 左子树总节点+右子树总节点+1

int size2(TreeNode root){
            if(root == null){
                return 0;
            }
            int leftsize = size2(root.left);
            int rightsize = size2(root.right);
            return leftsize+rightsize+1;
        }

![1bd4541364944f7495dd239874963968.png][]

## 3. 获取叶子节点的个数 ##

方法一：分解为子问题

代码

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);

![e71c6b711904430bbf347ffce72d8cae.png][]

方法二：遍历

定义一个计数器，当节点的左右子树同时为空时，说明这是叶子节点

代码

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);

![0777fa9c139341528e83eb88950e29e2.png][]

## 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);

## ![5cafcd8be2ba4f21994649ab30dc57c0.png][]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);

![463262a3bdac4b3a850eae72ae48d5fb.png][]

注意不要将返回值写成这样：

return  getHeight(root.left)>getHeight(root.right)
                    ? getHeight(root.left)+1:getHeight(root.right)+1;

这样会出现重复递归的情况，测试用例较多时会运行超时

## 6. 检测值为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);

![3dea765b2cde4d7c967bff29c7041546.png][]

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Apifox _ Postman _ Swagger _ Mock _ JMeter_Mock_ 10]: http://apifox.cn/a103liucf
[Link 2]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[Link 3]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[Link 4]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[25cc011b47c142578bf41a86db779d6d.png]: https://img-blog.csdnimg.cn/25cc011b47c142578bf41a86db779d6d.png
[464848b3b765441a9096fb30a88d97e3.png]: https://img-blog.csdnimg.cn/464848b3b765441a9096fb30a88d97e3.png
[1bd4541364944f7495dd239874963968.png]: https://img-blog.csdnimg.cn/1bd4541364944f7495dd239874963968.png
[e71c6b711904430bbf347ffce72d8cae.png]: https://img-blog.csdnimg.cn/e71c6b711904430bbf347ffce72d8cae.png
[0777fa9c139341528e83eb88950e29e2.png]: https://img-blog.csdnimg.cn/0777fa9c139341528e83eb88950e29e2.png
[5cafcd8be2ba4f21994649ab30dc57c0.png]: https://img-blog.csdnimg.cn/5cafcd8be2ba4f21994649ab30dc57c0.png
[463262a3bdac4b3a850eae72ae48d5fb.png]: https://img-blog.csdnimg.cn/463262a3bdac4b3a850eae72ae48d5fb.png
[3dea765b2cde4d7c967bff29c7041546.png]: https://img-blog.csdnimg.cn/3dea765b2cde4d7c967bff29c7041546.png