devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

《Java初阶数据结构》----5.＜二叉树的概念及使用＞

作者：知新_RL | 2024-08-05 01:51:21

赞

踩

《Java初阶数据结构》----5.＜二叉树的概念及使用＞

前言
大家好，我目前在学习java。之前也学了一段时间，但是没有发布博客。时间过的真的很快。我会利用好这个暑假，来复习之前学过的内容，并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论！！！
喜欢我文章的兄弟姐妹们可以点赞，收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦，我会持续更新滴，
望支持！！！！！！一起加油呀！！！！

语言只是工具，不能决定你好不好找工作，决定你好不好找工作的是你的能力！！！！！

学历本科及以上就够用了！！！！！！！！！！！！！！！！！！！！！！

【本章博客包含】
1.树的基本概念
2.二叉树概念及特性
3.二叉树的基本操作及方法模拟实现
4.二叉树相关的编程题练习

一、树的概念

1.1基本概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树。它是根朝上，而叶朝下的。

  • 它具有以下的特点：
  1. 有一个特殊的结点，称为根结点，根结点没有前驱结点
  2. 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti (1 <= i <=m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
  3. 树是递归定义的。

//注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2内部（重要）概念

在这里插入图片描述

1.结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6
2.树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6
3.叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I…等节点为叶结点
4.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
5.孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
6.根结点：一棵树中，没有双亲结点的结点；如上图：A
7.结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
8.树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G…等节点为分支结点
兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

1.3树的表示形式

双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。
最常用的：孩子兄弟表示法。

1.4树的应用

文件管理系统（目录和文件）

二、二叉树的概念

2.1概念

一棵二叉树是结点的一个有限集合，该集合：

  1. 或者为空
  2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
    在这里插入图片描述

二叉树特点：
1.二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：
在这里插入图片描述

2.2两种特殊的二叉树

  1. 满二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是，则它就是满二叉树。
  2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。

注意：满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

2.3二叉树的性质

  1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有(i>0)个结点
  2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是(k>=0)
  3. 对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1
  4. .具有n个结点的完全二叉树的深度k为log以2为低（n+1）上取整
  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
  • 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
  • 若2i+1<n，左孩子序号：2i+1，否则无左孩子
  • 若2i+2<n，右孩子序号：2i+2，否则无右孩子
    优先级队列

性质3的推导
节点：n = n1 + n2 + n3
边：e = 2n2 + n1 = n-1 （除根节点外每个节点对应一条边）
得出 2n2 + n1 = n1 + n2 + n3 -1
化简：n0= n2+ 1

2.4二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。
顺序存储在优先级队列文章介绍。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
} /

/ 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

孩子双亲表示法后序在平衡树位置介绍，本文采用孩子表示法来构建二叉树。

三、二叉树的基本操作

// 前序遍历
void preOrder(Node root);

// 中序遍历
void inOrder(Node root);

// 后序遍历
void postOrder(Node root);

// 获取树中节点的个数
int size(Node root);

// 获取叶子节点的个数
int getLeafNodeCount(Node root);
// 子问题思路-求叶子结点个数

// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k);

// 获取二叉树的高度
int getHeight(Node root);

// 检测值为value的元素是否存在
Node find(Node root, int val);

//层序遍历
void levelOrder(Node root);

// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

1.前序遍历

1.1 二叉树无返回值的前序遍历
    //二叉树无返回值的前序遍历
    public void prevOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
1.2 二叉树有返回值的前序遍历
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        ret.add(root.val);
        List<Character> leftTree = preorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree = preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

2.中序遍历

    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
    public List<Character>  inOrderTraversal(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        List<Character> leftTree = inOrderTraversal(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Character> rightTree = inOrderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.后序遍历

    //后序遍历
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
    public List<Character>  postOrderTraversal(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        List<Character> leftTree = inOrderTraversal(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree = inOrderTraversal(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

4.获取树中节点个数

    // 获取树中节点的个数
    public int size;
    int sizeNode(TreeNode root){
        if(root == null){
            return 0;
        }
        size++;
        sizeNode(root.left);
        sizeNode(root.right);
        return size;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
    int sizeNode2(TreeNode root){
        if(root == null){
            return 0;
        }
        return sizeNode2(root.left)+sizeNode2(root.right)+1;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

5.获取叶子节点的个数

    //5. 获取叶子节点的个数（左右都为空）
    int getLeafNodeCount1(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
    public int leafSize;
    void getLeafNodeCount2(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

子问题思路-求叶子结点个数

// 子问题思路-求叶子结点个数
    int getLeafNodeCount1(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
    //统计求解
    public int leafSize;
    void getLeafNodeCount2(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

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

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

7.获取二叉树的高度

    // 获取二叉树的高度
    int getHeight(TreeNode root){
        if(root ==null){
            return 0;
        }
        getHeight(root.left);
        getHeight(root.right);
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
    int getHeight1(TreeNode root){
        if(root ==null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left,right)+1;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
    int getHeight2(TreeNode root){
        if(root ==null){
            return 0;
        }

        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

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

    // 检测值为value的元素是否存在
    boolean findVal(TreeNode root, int val){
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        }
        boolean leftVal = findVal(root.left,val);
        if(leftVal){
            return true;
        }
        boolean rightVal = findVal(root.right,val);
        if(rightVal){
            return true;
        }
        return false;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

9.层序遍历

    //层序遍历(无返回值)
    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
    //有返回值为List<List<TreeNode>>的层序遍历
    public List<List<TreeNode>> levelOrder2(TreeNode root){
        List<List<TreeNode>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<TreeNode> temp = new ArrayList<>();
            while ((size!=0)){
                TreeNode cur = queue.poll();
                temp.add(cur);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
    //有返回值为List<List<Character>>的层序遍历
    public List<List<Character>> levelOrder3(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Character> temp = new ArrayList<>();
            while ((size!=0)){
                TreeNode cur = queue.poll();
                temp.add(cur.val);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

10.判断一棵树是不是完全二叉树

    public boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            else {//说明此时队列里全是空
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                return false;
            }
        }
        return true;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

1.首先如果这棵树为null，那么是完全二叉树返回true。

11.寻找节点路径问题

    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack ){
        if(root == null || node == null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg == true){
            return true;
            
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2 == true){
            return true;
            
        }
        stack.pop();
        return false;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

这个思想很简单。

1.如果树为null或节点为null那么没有找到路径，返回false。
2.接着将根节点添加到栈中。如果根节点为要找的节点。那么返回true。
3.接着去树的左边找，右边找。将每次路过的节点都添加到栈中。
4.如果左右两边都没有要找的节点。那么就弹出这个“根节点”。
5.最终栈留下来的就是我们要找的节点的路径了。返回true。

《Java数据结构》—二叉树的基本操作代码的具体实现

四、面试题练习

  1. 检查两颗树是否相同
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p != null && q == null || p == null && q != null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  1. 另一棵树的字树
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null){
            return false;//容易漏掉
        }
         
        if(isSameTree(root,subRoot)){
            return true;
        }

        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        
        return false; 
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p != null && q == null || p == null && q != null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  1. 翻转二叉树
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  1. 平衡二叉树
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }

        return biTreeHight(root)>=0;

    }
    public int biTreeHight(TreeNode root){
        if(root == null){
            return 0;
        }
        int hl = biTreeHight(root.left);
        int hr = biTreeHight(root.right);
        
        if(Math.abs(hl-hr)<=1&&hl>=0&&hr>=0){
            return Math.max(hl,hr)+1;
        }else{
            return -1;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  1. 对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);   
    }

    public boolean isSymmetricChild(TreeNode p,TreeNode q){
        if(p == null && q == null){
            return true;
        }
        if(p != null && q == null ||p == null && q != null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSymmetricChild(p.left,q.right)&& isSymmetricChild(p.right,q.left);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  1. 二叉树的构建及遍历
import java.util.Scanner;

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val){
        this.val = val;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
        String str = in.nextLine();
        TreeNode root = createTree(str);
        inOrder(root);
        }
    }
    public static int i = 0;
    public static TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            i++;
        }
        return root;
    }

    public static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  1. 二叉树的层序遍历
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            while ((size!=0)){
                TreeNode cur = queue.poll();
                temp.add(cur.val);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  1. 二叉树的最近公共祖先
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP>sizeQ){
            int size = sizeP-sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else{
             int size = sizeQ-sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }           
        }
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            if(stackP.peek().equals(stackQ.peek())){
                return stackP.peek();

            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack ){
        if(root == null || node == null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg == true){
            return true;
            
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2 == true){
            return true;
            
        }
        stack.pop();
        return false;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
//利用递归
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(p == root || q == root){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree!= null && rightTree != null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else{
            return rightTree;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  1. 根据一棵树的前序与中序遍历序列构造二叉树
class Solution {

    public int preIndex;//成员变量

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        //1.若没有左树或者没有右树
        if(inbegin>inend){
            return null;
        }

        //2.创建根节点
        TreeNode root = new TreeNode(preorder[preIndex]); 

        //3.从中序遍历中找到根节点下标
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1){
            return null;
        }

        preIndex++;

        //4.先创建左子树 后创建右子树
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin; i<= inend ; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  1. 根据一棵树的中序与后序遍历序列构造二叉树
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public int postIndex;//成员变量

    public TreeNode buildTree(int[] inorder,int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
        //1.若没有左树或者没有右树
        if(inbegin>inend){
            return null;
        }

        //2.创建根节点
        TreeNode root = new TreeNode(postorder[postIndex]); 

        //3.从中序遍历中找到根节点下标
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        if(rootIndex == -1){
            return null;
        }

        postIndex--;

        //4.先创建左子树 后创建右子树
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int key){
        for(int i = inbegin; i<= inend ; i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  1. 根据二叉树创建字符串
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return Integer.toString(root.val);
        }
        if (root.right == null) {
            return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")(").append(tree2str(root.right)).append(")").toString();
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  1. 二叉树的前序遍历(非递归实现)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        ret.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  1. 二叉树的中序遍历(非递归实现)
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        List<Integer> leftTree = inorderTraversal(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  1. 二叉树的后序遍历(非递归实现)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        List<Integer> leftTree = postorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/930309
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号