算法（Java）——二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法（Java）——二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10284字，纯文字阅读大概需要15分钟。

内容图文

二叉树在算法中也是比较常用的数据结构，根据二叉树的遍历算法，在算法题中遇到二叉树经常优先考虑递归算法。同时二叉树中的二叉搜索树也是常用的，主要结合中序遍历有序的特性。

二叉树

二叉树结构：

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

二叉树遍历主要分为前序、中序、后序和层次遍历。二叉树的深度优先搜索（DFS）和广度优先搜索（BFS）。

力扣关于二叉树的算法

1）剑指offer55_Ⅰ:二叉树的深度

题目：输入一棵二叉树的根节点，求该树的深度。

解题思路：递归左右子树的深度，最后比较左右子树深度加1。

算法代码：

class Solution { //递归实现
    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;
    }
}

2）剑指offer55_Ⅱ：平衡二叉树

题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解题思路：递归，先找树的深度，再根据树的深度递归判断平衡二叉树。

算法代码：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(getHeigth(root.left)-getHeigth(root.right))<=1){
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }
    public int getHeigth(TreeNode root){
        if(root==null) return 0;
        return Math.max(getHeigth(root.left),getHeigth(root.right))+1;
    }
}

3）剑指offer27：二叉树的镜像

题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路：递归左右子树的镜像，借助个临时节点暂时存储左（右）节点。

算法代码：

class Solution { //递归
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

4）剑指offer68_Ⅰ：二叉树最近公共祖先

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

解题思路：递归左右子树，判断情况：

一个左子树一个右子树
都在左子树
都在右子树
一个是自身，另一个在子树

算法代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null && right!=null) return root;  //一个左子树一个右子树，最近祖先是root
        if(left==null){  //都在左子树或都在右子树
            return right;
        }else{
            return left;
        }
    }
}

5）剑指offer31：从上到下打印二叉树Ⅰ

题目：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:

给定二叉树: [3,9,20,null,null,15,7],

[3,9,20,15,7]

解题思路：使用队列对二叉树进行层次遍历，即广度优先搜索BFS。返回一层，可以直接将节点存储到list中输出。

算法代码：

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null) return new int[0]; //new int[0] 表示动态分配一个长度为0的int数组
        Queue<TreeNode> queue = new LinkedList<TreeNode>();  //创建队列进行层次遍历
        ArrayList<Integer> list = new ArrayList<Integer>();  //创建list存储值
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
        }
        int[] res = new int[list.size()];  //将List中的值输出存储到int中
        for(int i=0;i<list.size();i++)
        {
            res[i]=list.get(i);
        }
        return res;
    }
}

6）剑指offer32：从上到下打印二叉树Ⅱ

题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解题思路：

从上到下按层打印又称为二叉树的广度优先搜索（BFS），BFS通常借助队列的先入先出特性来实现。同上。
每层打印到一行，将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即多行打印。

算法代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue  = new LinkedList<TreeNode>();
        List<List<Integer>> list = new ArrayList<>();  //List中再装一个List用来存储最后的结果
        if(root!=null) queue.offer(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> tmp = new ArrayList<Integer>(); //创建tmp存储一行节点
            for(int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
            list.add(tmp); //按行加入到list中          
        }
        return list;
    }
}

7）剑指offer28：对称的二叉树

题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

解题思路：考虑递归，递归root的左右子树。先判断root==null

左右节点都为空,true
左右一个空，false
左右节点不一样，false 值，左右，右左都镜像

算法代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return lrbinary(root.left, root.right);
    }
    public boolean lrbinary(TreeNode root1, TreeNode root2){
        if(root1==null && root2==null) return true;
        if(root1==null || root2==null) return false;
        return root1.val==root2.val && lrbinary(root1.left, root2.right) && lrbinary(root1.right, root2.left);
    }
}

其它二叉树算法

1）统计根节点到叶节点的路径的和

算法代码：

public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode p,int s){
        if(p ==null ){
            return 0;
        }
        if(p.left == null && p.right == null){
            return s*10 + p.val;
        }
        return dfs(p.left, s*10 +p.val) + dfs(p.right, s*10 +p.val);
    }

2）统计完全树节点的个数

解题思路：简单的方法是直接统计左右子树高度，若相等，则说明以该节点为跟的子树是满二叉树，直接返回 2^h-1 即可，若不是，则返回 count(左子树)+count(右子树)+1：

算法代码：

public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode p = root, q = root;
        int hl = 0, hr = 0;
        while(p != null){//统计左子树高
             p = p.left;
             hl ++;
        }
        while(q != null){//统计右子树高
             q = q.right;
             hr ++;
        }
        if(hl == hr) return (1 << hl) - 1;// <=> 2^hl - 1
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

3）二叉树非递归遍历

a.先序遍历

算法代码：

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new  ArrayList<Integer>();
        if(root == null) return res;
        LinkedList<TreeNode> s = new  LinkedList<TreeNode>();
        while(root != null || !s.isEmpty()){
           while(root!=null){
               s.push(root);
               res.add(root.val);
               root = root.left;
           }
           if(!s.isEmpty()){
               root = s.pop();
               root = root.right;
           }
        }
        return res;
    }

b.中序遍历

算法代码：

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();        //结果集
        LinkedList<TreeNode> s = new LinkedList<TreeNode>(); //辅助栈
        if(root == null) return res;
        while(root != null || !s.isEmpty()){
           while(root != null){
               s.push(root);
               root = root.left;
           }//此时 root 已经为空了
           if(!s.isEmpty()){
               root = s.pop();
               res.add(root.val);
               root = root.right;
           }
        }
        return res;
    }

c.后序遍历

（1）先序反转法
先序： root-left-right ，后序：需要 left-right-root，所以在先序的时候先放right再放left得到 root-right-left ，然后反转即可。

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        LinkedList<TreeNode> s = new LinkedList<TreeNode>();
        if(root == null) return res;
        while(root != null || !s.isEmpty()){
            while(root != null){
                s.push(root);
                res.add(root.val);
                //不同于 preOrder 这里先右
                root = root.right; 
            }
            if(!s.isEmpty()){
                root = s.pop();
                root = root.left;
            }
        }
        Collections.reverse(res);
        return res;//翻转再返回结果就好
 }

（2）双栈法

其实就是利用两个栈构造出 root-right-left 的序列，然后出栈即为反转了，不如上一个快

给两个栈 s1，s2;

将root入s1;

若s1非空，将s1的栈顶元素赋给root，然后将root入s2；然后先将root左结点入s1，后将root右结点入s1，顺序不能错;

若s2非空，出s2，就获得后序遍历;

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<Integer>();
        //两个 stack  ，一个 stack按跟左右进栈
        //放到另一个stack，形成 跟 右左，然后出栈即得到结果
        LinkedList<TreeNode> s1 = new LinkedList<TreeNode>();
        LinkedList<TreeNode> s2 = new LinkedList<TreeNode>();
        if(root == null) return res;
        s1.push(root);
        while(!s1.isEmpty()){
            root = s1.pop();
            s2.push(root);
            if(root.left != null) 
                s1.push(root.left);
            if(root.right!= null) 
                s1.push(root.right);
        }
        while(!s2.isEmpty())
            res.add(s2.pop().val);
        return res;
}

d.层次遍历

这里直接给出层次遍历的分层打印方法，用parent 与 children 两个变量分别统计当前层与下一层的节点数，每次拿出一个节点，当前层计数 parent-1；当parent == 0；输出一个换行符，然后另 parent = children ，children =0 即可。

public void lfs(Node root) {
           if(root == null) return ;
           //十分万能的，当队列或者栈都可以用的 LinkedList。
           LinkedList<Node> queue = new LinkedList<Node>();
           queue.add(root);
           int parent = 1;
           int children = 0;
           while(!queue.isEmpty()){
                System.out.print(queue.peek() +" ");
                Node cur = queue.removeFirst();
                --parent; 
                if(cur.left  != null) {queue.addLast(cur.left ); ++children;}
                if(cur.right != null) {queue.addLast(cur.right); ++children;}
                if(parent == 0) {System.out.println(); parent = children; children = 0;}
           }
        }

二叉搜索树

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

因此，二叉搜索树的特点：中序遍历是顺序的。是经常用的考察点。

力扣关于二叉搜素树的算法

1）剑指offer54：二叉搜索树的第k大节点

题目：给定一棵二叉搜索树，请找出其中第k大的节点。

解题思路：中序遍历顺序，左根右从小到大，逆序右根左。

示例 1:

输入: root = [3,1,4,null,2], k = 1

输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

输出: 4

算法代码：

class Solution {  //中序遍历左根右顺序，右根左逆序，第k大，所以用逆序
    private int ans=0, count=0;
    private void Middle(TreeNode root, int k){
        if(root == null) return;
        Middle(root.right,k);
        if(++count==k){
            ans=root.val;
        }    
        Middle(root.left,k);
    }
    public int kthLargest(TreeNode root, int k) {
        Middle(root,k);
        return ans;
    }
}

2）剑指offer68_Ⅱ:二叉搜索树的最近公共祖先

题目：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

解题思路：要利用二叉搜索树的性质，左子树都比根小，右子树都比根大，与一般的二叉树相比，只需要与根的值比较就可以判断左右子树，不需要具体到节点。

算法代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p,TreeNode q) {
        if(root==null) return null;
        if(root.val>p.val && root.val>q.val) //说明在左子树
            return lowestCommonAncestor(root.left, p, q);
        else if(root.val<p.val && root.val<q.val) //说明在右子树
            return lowestCommonAncestor(root.right, p, q);
        else  //各在一边
            return root;
    }
}

内容总结

以上是互联网集市为您收集整理的算法（Java）——二叉树全部内容，希望文章能够帮你解决算法（Java）——二叉树所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/598932.html

来源：【匿名】

【上一篇】二分查找算法的非递归调用与递归调用实现【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【算法（Java）——二叉树】教程文章相关的互联网学习教程文章

版权所有。所有权利保留。欢迎转载，转载时请注明出处：http://blog.csdn.net/xiaofei_it/article/details/51502727为了防止思维僵化，每天刷个算法题。已经刷了几天了，现在发点代码。我已经建了一个开源项目，每天的题目都在里面：https://github.com/Xiaofei-it/Algorithms绝大部分算法都是我自己写的，没有参考网上通用代码。读者可能会觉得有的代码晦涩难懂，因为那是我自己的理解。最近几天都是在写一些原来的东西，大多数是...

Python -二叉树创建与遍历算法(很详细）【代码】

树表示由边连接的节点。它是一个非线性的数据结构。它具有以下特性。一个节点被标记为根节点。除根节点之外的每个节点都与一个父节点关联。每个节点可以有一个arbiatry编号的chid节点。我们使用前面讨论的os节点概念在python中创建了一个树数据结构。我们将一个节点指定为根节点，然后将更多的节点添加为子节点。下面是创建根节点的程序。创建树创建根我们只需要创建一个节点类并向节点添加赋值。这就变成了只有根节点的树。 1clas...

[算法题] 重建二叉树【代码】

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。题目思路本题就是按照建立二叉树的思路建立就行了。先序遍历的第一个是根节点，然后在中序遍历找到该根节点，以此为界，中序遍历的左边是它的左子树的中序遍历，同样地找到该左子树在先序遍历中对应的先序遍历顺序。对于右子树也是一样的方法。本体采用递归，递归就要先写出终止条件。Python代码这个题...

新手算法学习之路----二叉树（二叉树最大路径和）【代码】

摘抄自：https://segmentfault.com/a/1190000003554858#articleHeader2题目：Given a binary tree, find the maximum path sum.The path may start and end at any node in the tree.For example: Given the below binary tree, 1/ 2 3 Return 6.思路：首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。第一种是左子树的路径加上当前节点，第二种是右子树的路径加上当前节点，第三种是左右子树的路径加上...

【数据算法】Java实现二叉树存储以及遍历【代码】

二叉树在java中我们使用数组的形式保存原数据，这个数组作为二叉树的数据来源，后续对数组中的数据进行节点化操作。步骤就是原数据：数组节点化数据：定义 Node节点对象存储节点对象：通过LinkedList保存Node节点对象在操作过程中我们需要将当前结点和前一节点、后一节点进行关系绑定 package tree; import java.util.LinkedList; import java.util.List; /** * 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历 *...

二叉树三种遍历算法的递归和非递归实现（C++）

struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight; }; //递归前序遍历 void PreOrder(BinaryTreeNode* pNode) {if(pNode!=NULL){cout<<pNode->m_nValue<<endl;PreOrder(pNode->m_pLeft);PreOrder(pNode->m_pRight);} } //非递归前序遍历 /* 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其...

二叉树中序遍历Joseph M. Morris算法【代码】

二叉树中序遍历，一种方法是递归，leetcode上的非递归方法有一种是用栈实现的，想来也没多大优化，手动递归比自动递归也快不了多少。还有一种不用栈的非递归方法，是Joseph M. Morris发明的，这位元老就是KMP算法中的M。下面代码来自贴吧大神，经测试可用。我还没研究具体是个怎么回事，时间上能达到100%vector<int> inorderTraversal(TreeNode* p) {vector<int> res;TreeNode* r = nullptr;while (p) {TreeNode* q = p->left;if (...

数据结构+算法第二天排序算法二叉树排序二叉树【代码】【图】

顺序查找查找原理:从列表中的第一个元素开始,我们按照基本的元素排序,简单的从一个元素移动到另一个元素,直到找到我们要找的元素或是遍历完整个列表.实例代码:def search(item,alist):find=Falselength=len(alist)for i in range(length):if alist[i] == item:find=Truereturn find对有序列表进行循环会提升查找的效率:def search(alist,item):find=Falselength=len(alist)pos=0stop=Falsewhile pos <=length andnot stop:if alist...

数据结构与算法系列----平衡二叉树（AVL树）【图】

一：背景平衡二叉树（又称AVL树）是二叉查找树的一个进化体，由于二叉查找树不是严格的O(logN)，所以引入一个具有平衡概念的二叉树，它的查找速度是O(logN)。所以在学习平衡二叉树之前，读者需要了解二叉查找树的实现，具体链接：二叉查找树那么平衡是什么意思？我们要求对于一棵二叉查找树，它的每一个节点的左右子树高度之差不超过1。（对于树的高度的约定：空节点高度是0；叶子节点高度是1。）例如下图：如果我们的二叉查找树是...

让我们来写个算法吧，（2）二叉树的前序，中序，后序遍历【代码】【图】

树的类结构publicclass TreeNode {TreeNode left;TreeNode right;int value;public TreeNode(int value ) {this.value = value;}}自己生成二叉树 private TreeNode createTreeNode() {TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树for (int i = 0; i < 10; i++) {node[i] = new TreeNode(i);}for (int i = 0; i < 10; i++) {if (i * 2 + 1 < 10)node[i].left = node[i * 2 + 1];if (i * 2 + 2 < 10)node[i]...

数据结构与算法之美专栏学习笔记-二叉树基础(下）【代码】【图】

二叉查找树 Binary Search Tree 二叉查找树的定义二叉查找树又称二叉搜索树。其要求在二叉树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树的节点的值都大于这个节点的值。二叉查找树的查找操作二叉树类、节点类以及查找方法的代码实现先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中...

剑指offer 6 重建二叉树【代码】

不用迭代器的代码class Solution { public:TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {TreeNode* root = NULL;int length_pre = pre.size();int length_vin = vin.size();if(length_pre <= 0 || length_vin <= 0)return root;return ConstructCore(pre,vin,0,length_pre-1,0,length_vin-1);}TreeNode* ConstructCore(vector<int> pre,vector<int> vin,int start_pre,int end_pre,int start_vin,int end_v...

二叉树的前中后序递归和非递归遍历操作【代码】

“遍历”是二叉树各种操作的基础，可以在遍历过程中对节点进行各种操作，如：求节点的双亲，求节点的孩子，判断节点的层次，当然，还有一些更重要的操作，例如，依据遍历序列建立二叉树，，再如，对建立的二叉树进行线索化，等等。二叉树的各种遍历操作必须了然于心，无论是递归的，还是非递归的。递归算法的优点是形式简单，当然，正如一句话所说“迭代是人，递归是神。”递归算法的整个详细过程还是很烧脑的，每一步都把未知当作...

4.3---建立高度最小二叉树【代码】

1，并没有把高度和建表结合了。而是最后才算。下一次可以想想怎么结合到一块去。1，建表（参考自书本）privatestatic TreeNode createMinimalBST(int arr[], int start, int end){if (end < start) {returnnull;}int mid = (start + end) / 2;TreeNode n = new TreeNode(arr[mid]);n.setLeftChild(createMinimalBST(arr, start, mid - 1));n.setRightChild(createMinimalBST(arr, mid + 1, end));return n;}publicstatic TreeNode ...

c++实验7 二叉树【代码】【图】

二叉树数据结构表示及基本操作算法实现1、所加载的库函数或常量定义及类的定义：#include<stdlib.h> #include<stdio.h> #include"BiTreeNode.h" #include<iostream> usingnamespace std; template <class T> class BiTree { private:BiTreeNode<T> *root; //根结点指针void Destroy(BiTreeNode<T>* &t);void InOrder(BiTreeNode<T> *&t, void (*Visit)(T item));void PostOrder(BiTreeNode<T>* &t, void (*Visit)(T ite...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 算法（Java）——二叉树

算法（Java）——二叉树

内容导读

内容图文

二叉树

力扣关于二叉树的算法

1）剑指offer55_Ⅰ:二叉树的深度

2）剑指offer55_Ⅱ：平衡二叉树

3）剑指offer27：二叉树的镜像

4）剑指offer68_Ⅰ：二叉树最近公共祖先

5）剑指offer31：从上到下打印二叉树Ⅰ

6）剑指offer32：从上到下打印二叉树Ⅱ

7）剑指offer28：对称的二叉树

其它二叉树算法

1）统计根节点到叶节点的路径的和

2）统计完全树节点的个数

3）二叉树非递归遍历

a.先序遍历

b.中序遍历

c.后序遍历

d.层次遍历

二叉搜索树

力扣关于二叉搜素树的算法

1）剑指offer54：二叉搜索树的第k大节点

2）剑指offer68_Ⅱ:二叉搜索树的最近公共祖先

内容总结

内容备注

内容手机端

【算法（Java）——二叉树】教程文章相关的互联网学习教程文章

JAVA - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程