小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

Java数据结构-二叉树

作者：小丑西瓜9 | 2024-04-20 11:45:15

踩

Java数据结构-二叉树

1. 树与二叉树

1.1 树

树是一种数据结构，它是由n(n≥0)个有限结点组成一个具有层次关系的集合。它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子节点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。如图所示：
在这里插入图片描述

1.2 二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

1.3 树的相关概念

在这里插入图片描述

结点的度： 一个结点含有的子树个数叫度，如图结点A的度为2，结点C的度为1，结点G的度为0
树的度： 一棵树中，所有结点度的最大值，如图树的度为2,
叶子结点(终端结点)： 度为0的结点叫叶子结点，如图G、H、I、F是叶子结点
孩子结点： 一个结点的子树的根节点叫孩子结点，如图A的孩子结点是C
根节点： 一棵树中，没有双亲结点的结点叫根节点
树的层次： 从根节点开始，根节点为第一层，根节点的孩子为第二层，以此类推
树的高度或深度： 树中所有节点的层次最大值，如图树的高度为4

1.4 特殊的二叉树

满二叉树： 如果一棵二叉树中，所有的结点的度要么是2，要么是0，这棵二叉树就是满二叉树，如图：
在这里插入图片描述
完全二叉树： 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。如图
在这里插入图片描述

1.5 二叉树性质

1、一棵非空二叉树的第i层上最多有2 ^ (i-1) （i>0）个结点(规定根节点的层数为1)
2、深度为k的二叉树的最大结点个数为(2^k )-1（k>=0）
3、设叶子结点的个数为n0，度为2的结点个数为n2，则有n0 = n2 +1
4、 n个结点的完全二叉树，深度为log2（n+1）向上取整
5、一棵完全二叉树，对每个结点从上到下从左到右进行编号(根节点为0)，序号为i的结点：
（1）左孩子结点的编号为2i+1，如果2i+1>n则没有左孩子
（2）右孩子结点的编号为2i+2，如果2i+1>n则没有右孩子
（3）如果i>0，双亲结点的编号为(i-1)/2

1.6 二叉树的存储与表示方法

二叉树的存储形式有两种，一种是链式存储，一种是顺序存储。链式存储是指通过引用来实现的，顺序存储是使用数组来实现的，今天主要介绍链式存储，顺序存储会在堆中介绍到。二叉树表示方法有孩子表示法、双亲表示法

//孩子表示法
class TreeNode {
	int val;//数据域
	TreeNode left;//左孩子的引用
	TreeNode right;//右孩子的引用
}
1
2
3
4
5
6

//双亲表示法
class TreeNode {
	int val;
	TreeNode left;//左孩子的引用
	TreeNode right;//右孩子的引用
	TreeNode parent;//双亲的引用
}
1
2
3
4
5
6
7

比较常用的是孩子表示法

2. 二叉树遍历

二叉树的遍历分为前序遍历、中序遍历、后序遍历、层序遍历，为了方便理解，我们定义一个类，如下:

public class Tree {
	//树的结点
    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子

        public TreeNode(char val) {
            this.val = val;
        }
    }
    
}

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

接着使用枚举的方法创建一棵如图的二叉树，至于如何正确的创建一棵二叉树，我们在后续的OJ题中会介绍到
在这里插入图片描述

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        TreeNode I = new TreeNode('I');
        A.left = C;
        A.right = B;
        C.left = D;
        D.left = G;
        D.right = H;
        B.left = E;
        B.right = F;
        E.left = I;
        return A;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这样我们就创建好了我们想要的二叉树。

2.1 前序遍历

访问顺序：根节点->根的左子树->根的右子树
在这里插入图片描述
前序遍历结果为：A C D G H B E I F

按照前序遍历的规则，访问完A结点后，接着该访问A的左子树，对于红色框部分来说又是一棵树，也需要按照前序遍历的规则访问，同理蓝色部分也是如此，所以我们可以使用递归的方式来遍历
在这里插入图片描述
代码实现：

    //前序遍历
    public void preOrder(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

2.2 中序遍历

访问顺序：根的左子树->根节点->根的右子树
在这里插入图片描述
中序遍历的结果为：G D H C A I E B F
与前序遍历一样，使用递归的方式遍历
代码实现：

    //中序遍历
    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
9

2.3 后序遍历

访问顺序：根的左子树->根的右子树->根节点
在这里插入图片描述
后序遍历的结果为：G H D C I E F B A
与前序遍历一样，使用递归的方式遍历
代码实现：

    //后序遍历
    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

2.4 层序遍历

遍历规则：从根节点开始，第一层的结点，访问完第一层后，接着访问第二层的所有结点（按从左到右的顺序），如图
在这里插入图片描述
层序遍历结果为：A C B D E F G H I
层序遍历的实现，需要借助另一个数据结构：队列
逻辑如图：

代码实现：

    //层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val + " ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 二叉树基本操作

3.1 求树的所有结点个数

可以使用递归的思路求解：树的结点个数 = 左子树所有结点个数 + 右子树所有结点个数 + 1(一棵树根节点只有一个)，如果树为空则返回0，而递归的结束条件刚好就是root为空
在这里插入图片描述

    //求结点个数
    public int NodeSize(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return NodeSize(root.left) + NodeSize(root.right) + 1;
    }
1
2
3
4
5
6
7

3.2 求叶子结点个数

递归的思路求解：一棵树的叶子结点个数=左子树的叶子结点个数+右子树的叶子结点个数
递归的结束条件：如果左孩子和右孩子都为空，返回1；如果结点为空，返回0

    //求叶子结点个数
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
1
2
3
4
5
6
7
8
9
10

3.3 求第k层结点个数

递归的思路求解：第k层的结点个数 = 左子树的第k-1层的结点个数 + 右子树的第k-1层的结点个数
递归的结束条件：如果root为空，返回0；如果k=1，说明已经到达第k层了，返回1

    //第k层结点的个数
    public 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
11

3.4 求二叉树的高度

递归的思路求解：二叉树的高度 = max（左子树的高度，右子树的高度）+ 1，因为树的高度是指最大高度，所以是左子树高度和右子树高度取最大的那个+1
递归的结束条件：当root为空时，返回0，空树的高度为0

    //树的高度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int LeftHeight = getHeight(root.left);//左子树的高度
        int RightHeight = getHeight(root.right);//右子树的高度

        return Math.max(LeftHeight, RightHeight) + 1;
    }
1
2
3
4
5
6
7
8
9
10

3.5 检测树中是否存在值为val的结点

递归的思路求解：可以采用前序遍历，只不过我们把访问换成了比较，思路都是一样的

    public boolean find(TreeNode root, char key) {
        if (root == null) {
            return false;
        }
        //判断根结点
        if (root.val == key) {
            return true;
        }
        //判断左子树
        boolean flg1 = find(root.left,key);
        if (flg1) {
            return true;
        }
        //判断右子树
        boolean flg2 = find(root.right,key);
        if (flg2) {
            return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.5 判断树是否为完全二叉树

代码：

    //是否为完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            if (top == null) {
                break;
            }
            queue.offer(top.left);
            queue.offer(top.right);
        }    
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.peek();
            if (tmp != null) {
                return false;
            } else {
                queue.poll();
            }
        }

        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
25
26

思路与层序遍历的逻辑有点类似，只不过这次不管top的左和右是不是空，我们都入队，如果top为空循环结束。如果树是完全二叉树，此时队列中剩余的元素全是null，如果队列中有不为null的元素，说明这棵树不是完全二叉树（如图）
在这里插入图片描述

4. 二叉树相关OJ题

4.1 相同的树

在这里插入图片描述
题目链接： 相同的树
题目要求： 给定2个二叉树的根节点p、q，判断这两棵树是不是同一棵树（树的结构一样、每个结点的值一样，说明是同一棵树）
解题思路： 递归思路：先判断两棵树的根节点结构是否相同，有两种情况：两个结点都为空、一个结点为空一个结点不为空、两个结点都不为空。如果两个结点都为空，认为两棵树是相同的；如果一个结点为空一个结点不为空，认为两棵树不是相同的；如果两个结点都不为空，说明结构是相同的。结构相同之后，判断两个结点的值是否相同，如果相同，证明了两棵树根节点是相同的，接着需要递归判断两棵树的左子树、右子树是否相同
代码：

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            // p、q都为空,认为是相同的树
            return true;
        }
        if (p == null || q == null) {
        	//一个为空,一个不为空,此时结构不相同,不是相同的树
            return false;
        }
        //以上代码走完,证明两个根节点的结构是相同的,还需要判断两个结点的值是否相同
        if (p.val != q.val) {
            // 根节点的val不同,返回false
            return false;
        } else {
            // 此时根节点判断结束,接着递归判断左右子树
            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

4.2 另一棵树的子树

在这里插入图片描述
题目链接：另一棵树的子树
题目要求： 给定两棵树的根节点：root、subRoot，判断subRoot这棵树是否为root这棵树的子树
解题思路： 递归思路：判断subRoot和root是不是相同的树、判断subRoot是不是root的左子树的子树、判断subRoot是不是root的右子树的子树，三个条件只要满足一个就认为subRoot是root的子树

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return isSubtree(root.left, subRoot) ||
                isSubtree(root.right, subRoot) || isSametree(root, subRoot);
    }

    public boolean isSametree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (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

4.3 翻转二叉树

在这里插入图片描述
题目链接： 翻转二叉树
题目要求： 给定一棵二叉树的根节点，要求翻转这棵树
解题思路： 交换根节点的左右结点，翻转完根节点的左右结点，接着递归翻转左子树与右子树
代码：

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.4 二叉树的最大深度

在这里插入图片描述
题目链接： 二叉树的最大深度
题目要求： 求二叉树的最大深度
解题思路： 递归思路：二叉树的最大深度 = 左子树最大深度与右子树最大深度的最大值 + 1，递归的结束条件为：当root=null时，返回0
代码：

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
1
2
3
4
5
6

4.5 平衡二叉树

在这里插入图片描述

题目链接： 平衡二叉树
题目要求：
解题思路：
代码：
优化前：

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) {
            //if 语句:判断根节点这棵树是否为平衡二叉树,如果根节点这棵树是,则需要递归判断左子树和右子树
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }
	public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

以上代码有一个缺点：当第一次递归左子树和右子树的时候就已经知道了左右子树的高度，接着又就行递归求高度，重复计算了树的高度，能不能进行改进？
优化后：

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return maxDepth(root)>=1;
    }

    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int LeftHeight = maxDepth(root.left);
        if(LeftHeight<0) {
        	//因为代码是递归进行的,LeftHeight可能为-1
            return -1;
        }
        int RightHeight = maxDepth(root.right);
        if(RightHeight<0) {
           //因为代码是递归进行的,RightHeight可能为-1
            return -1;
        }
        if(Math.abs(LeftHeight-RightHeight)<=1) {
            //平衡的,返回树的最大深度即可
            return Math.max(LeftHeight,RightHeight)+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
24
25
26
27
28
29

4.6 对称二叉树

在这里插入图片描述

题目链接： 对称二叉树
题目要求： 给定一棵二叉树的根节点，判断这棵树是否为对称二叉树，对称的意思是，左右结构相同，结点的值也相同，如实例所示
解题思路： 先判断给定的root是否为空，如果不为空，则进行递归判断，因为题目给的方法只有一个参数，所以我们另写一个isSymmetricChild方法，参数为左结点left，右结点right。在isSymmetricChild方法中进行递归求解。传递的left和right有三种情况：1.两个都为空，此时认为是对称二叉树，2.一个为空一个不为空，此时一定不是对称二叉树，2.两个都不为空，这种情况下，还需要判断left结点和right结点的值是否相等，如果不相等则不是对称二叉树，如果相等，根据示例的二叉树我们可以知道，需要递归判断left的左子树和right的右子树，left的右子树和right的左子树
在这里插入图片描述

代码：

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

    public boolean isSymmetricChild(TreeNode left, TreeNode right) {
        // 左右:一个为空,一个不为空;两个都为空;两个都不为空
        // 两个都为空,认为也是对称的
        if (left == null && right == null) {
            return true;
        }
        // 一个为空,一个不为空
        if (left == null && right != null || left != null && right == null) {
            return false;
        }
        // 此时,两个都不为空了,判断结点的值是否相同
        if (left.val == right.val) {
            return isSymmetricChild(left.left, right.right) 
            && isSymmetricChild(left.right, right.left);
        } else {
            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

4.7 二叉树创建及遍历

在这里插入图片描述

题目链接： 二叉树遍历
题目要求： 给定二叉树的前序遍历的字符串序列，根据这个字符串创建二叉树，并且输出这棵二叉树的中序遍历（#字符表示空树）
解题思路： 首先，题目只告诉了我们前序遍历，能不能确定它是唯一的树？可以！因为它告诉了我们哪个结点是空的！前序遍历我们已经了如指掌，我们只需要知道怎么创建这棵树就好了。因为题目给我们的是前序遍历，那我们也根据前序遍历来创建二叉树。定义一个变量a用于遍历输入的字符串，如果a下标的字符不是#，我们就创建根节点，让根节点的值等于这个字符，接着让a++，接着递归创建左子树和右子树，如果a下标是#，只需要让a++
代码：

class TreeNode {
    char val;//结点的值
    TreeNode left;//左
    TreeNode right;//右

    public TreeNode() {

    }

    public TreeNode(char val) {
        this.val = val;
    }
}


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int a;//用于遍历字符串

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

    //前序遍历创建二叉树
    public static TreeNode createTree(String str) {
        char ch = str.charAt(a);
        TreeNode root = null;//创建根节点
        if (ch != '#') {
            root = new TreeNode(ch);
            a++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            a++;
        }
        return root;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = new String();
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            str = in.nextLine();
        }
        TreeNode root = createTree(str);
        inOrder(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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

4.8 二叉树的层序遍历

在这里插入图片描述

题目链接： 二叉树的层序遍历
题目要求： 给定二叉树的根节点，返回层序遍历的结果，注意返回值的类型，
List<List< Integer>>，实际上就是一个二维数组，
解题思路： 层序遍历我们之前写过了，原理都是一样，只不过我们需要确定每一层的元素个数，定义一个List< Integer >类型的变量 list，然后将某一层的元素都添加到list中，遍历完一层就将list添加至List<List< Integer>>类型的变量ret中
代码：

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();// 需要返回的
        Queue<TreeNode> queue = new LinkedList<>();// 使用队列来进行层序遍历
        if (root == null) {
            return ret;
        }
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();//每一层的元素个数
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                list.add(tmp.val);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
            ret.add(list);//遍历完一层,将list添加到ret中
        }

        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

4.9 二叉树的最近公共祖先

在这里插入图片描述

题目链接： 二叉树的最近公共祖先
题目要求： 给定一棵二叉树，找到两个指定结点的公共祖先，
解题思路：
可能出现以下情况：
在这里插入图片描述
1.如果p或者q其中一个是等于root，那么公共祖先是root；2.p和q分别树的在左右两边；3.p和q在树的左边；4.p和q在树的右边
方法1： 递归法：第一步判断情况1，如果情况1满足返回root，接着递归左子树和右子树，定义变量LeftTree和RightTree，根据LeftTree和RightTree的值是否为空可以判断其余3种情况
方法2： 类似于链表求公共结点，只要求出根节点到p结点和根节点到q结点的公共结点即可，将根节点到p结点的路径上的所有结点和根节点到q结点的路径上的所有结点分别放入两个栈中，两个栈的元素可能不同，所以先出元素多的栈，出差值个元素，这样两个栈的元素就一样了，接着两个栈一起出元素，判断出栈的元素是否相等，如果相等就说明该结点是公共结点，也就是公共祖先。难点是如何求根节点到p或q的路径上的结点，思路：利用递归求解，在递归的过程中，不管root是不是我们需要的结点，先入栈root结点，判断root是不是指定结点、root的左子树和右子树中有没有指定结点，如果root不是指定的结点、root的左子树和右子树中都没有指定结点，则说明入栈了的这个结点不是我们想要的，此时出栈这个元素，以此类推直到递归结束
在这里插入图片描述

代码：
方法1

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            // 情况1
            return root;
        }
        TreeNode LeftTree = lowestCommonAncestor(root.left, p, q);// 递归左边
        TreeNode RightTree = lowestCommonAncestor(root.right, p, q);// 递归右边
        if (LeftTree != null && RightTree != null) {
            return root;//情况2
        }
        if (LeftTree != null) {
            return LeftTree;//情况3
        }
        if (LeftTree == null) {
            return RightTree;//情况4
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法2

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
            return root;
        }
        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.isEmpty()) {
                stackP.pop();
                size--;
            }
        }
        if (sizeP < sizeQ) {
            int size = sizeQ - sizeP;
            while (size > 0 && !stackQ.isEmpty()) {
                stackQ.pop();
                size--;
            }
        }

        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek().equals(stackQ.peek())) {
                return stackP.peek();
            } else {
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }
    // 获取路径上的所有结点
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        // 判断根节点是否指定结点
        if (root == node) {
            return true;
        }
        boolean left = getPath(root.left, node, stack);
        // 判断左子树是否包含指定结点
        if (left) {
            return true;
        }
        boolean right = getPath(root.right, node, stack);
        // 判断右子树是否包含指定结点
        if (right) {
            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
58
59

4.10 已知中序与前序遍历构造二叉树

在这里插入图片描述

题目链接： 已知前序遍历与中序遍历构造二叉树
题目要求： 给定前序遍历和中序遍历的数组，构造二叉树，返回根节点
解题思路： 需要知道的前提是：前序遍历的第一个是结点是根节点，定义preindex，用于遍历preorder数组。ib表示开始位置，ie表示结束位置，如图1：在中序遍历数组中，ib和ie区间内寻找E的下标，接着创建E结点，在中序遍历中，E的左边就是左子树，E的右边就是右子树，E结点创建好之后，递归创建E的左子树和右子树，如图2，递归左子树时，ib不变，ie变成rootIndex-1，递归右子树时，ie不变，ib变成rootIndex+1，所以我们得知道rootindex。递归结束的条件就是ib>ie（当ib=ie表示还有一个结点，不能结束）
在这里插入图片描述

代码：

class Solution {
    public int preindex;

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

    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int ib, int ie) {
        if (ib > ie) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preindex]);
        int rootIndex = findRootIndex(inorder, ib, ie, preorder[preindex]);
        preindex++;//找到rootIndex之后才能让preindex++
        root.left = buildTreeChild(preorder, inorder, ib, rootIndex - 1);// 递归左
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, ie);// 递归右
        return root;
    }

	//找rootindex的下标
    private int findRootIndex(int[] arr, int start, int end, int key) {
        for (int i = start; i <= end; i++) {
            if (arr[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

4.11 已知中序与后序遍历构造二叉树

在这里插入图片描述

题目链接： 已知中序与后序遍历构造二叉树
题目要求： 给定后序遍历和中序遍历的数组，构造二叉树，返回根节点
解题思路： 和前序遍历的思路差不多，但是后序遍历的最后一个元素才是根节点，所以需要从后往前遍历，另外，递归的顺序是根、右、左
在这里插入图片描述

代码：

class Solution {
    public int postIndex;

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

    public TreeNode buildTreeChild(int[] inorder, int[] postorder, int ib, int ie) {
        if (ib > ie) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findRootIndex(inorder, ib, ie, postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild(inorder, postorder, rootIndex + 1, ie);// 递归右
        root.left = buildTreeChild(inorder, postorder, ib, rootIndex - 1);// 递归左
        return root;
    }

    private int findRootIndex(int[] arr, int start, int end, int key) {
        for (int i = start; i <= end; i++) {
            if (arr[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

4.12 根据二叉树创建字符串

在这里插入图片描述

题目链接： 根据二叉树创建字符串
题目要求： 采用前序遍历的方式将二叉树转换为由括号和数字组成的字符串
解题思路：
在这里插入图片描述

代码：

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root,str);
        return str.toString();
    }
    private void tree2strChild(TreeNode root,StringBuilder str) {
        if(root==null) {
            return;
        }
        str.append(root.val);//处理根结点
        //处理左树        
        if(root.left!=null) {
            //root的左不为空
            str.append("(");//拼接左括号
            tree2strChild(root.left,str);//递归左树
            str.append(")");//拼接右括号
        } else {
            //root的左为空
            if(root.right==null) {
                //root右也为空
                return;
            } else{
                //root的右不为空
                str.append("()");
            }
        }
        //处理右树
        if(root.right==null) {
            return;
        } else {
            str.append("(");
            tree2strChild(root.right,str);
            str.append(")");
        }
    }
}
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

4.13 二叉树的前序遍历(递归与非递归)

在这里插入图片描述
题目链接： 二叉树的前序遍历
题目要求： 给定根节点，返回前序遍历
解题思路： 1.非递归法：利用栈来实现,过程如图，2.递归和之前的递归是一样的这里不多赘述

代码：
非递归法

    public List<Integer> preorderTraversal(TreeNode root) {        
        List<Integer> list = new LinkedList<>();
        if(root==null) {
            return list;
        }
        //...
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

递归法

    List<Integer> list = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {        
        if(root==null) {
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
1
2
3
4
5
6
7
8
9
10

4.14 二叉树的中序遍历(递归与非递归)

在这里插入图片描述

题目链接： 二叉树的中序遍历
题目要求： 给定根节点，返回中序遍历
解题思路： 1.非递归法：利用栈来实现,过程如图，2.递归和之前的递归是一样的这里不多赘述
在这里插入图片描述

代码：
非递归法

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        //.........
        if(root==null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //左走完了
            TreeNode top = stack.pop();
            //
            list.add(top.val);
            //再往右
            cur = top.right;
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归法

    List<Integer> list = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) {
    return list;
    }
    inorderTraversal(root.left);
    list.add(root.val);
    inorderTraversal(root.right);
    return list;
    }
1
2
3
4
5
6
7
8
9
10

4.15 二叉树的后序遍历(递归与非递归)

在这里插入图片描述

题目链接： 二叉树的后序遍历
题目要求： 给定根节点，返回后序遍历
解题思路： 1.非递归法：利用栈来实现,过程如图，2.递归和之前的递归是一样的这里不多赘述
在这里插入图片描述

代码：
非递归法

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root==null) {
            return list;
        }
        //.................
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode flg = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == flg) {
                stack.pop();
                list.add(top.val);
                flg = top;
            } else {
                cur = top.right;
            }
        }
        return list;
    }
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

递归法

    List<Integer> list = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null) {
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
1
2
3
4
5
6
7
8
9
10

今天的内容就到这里，感谢大家的支持！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/457116

Java数据结构-二叉树

目录

1. 树与二叉树

1.1 树

1.2 二叉树

1.3 树的相关概念

1.4 特殊的二叉树

1.5 二叉树性质

1.6 二叉树的存储与表示方法

2. 二叉树遍历

2.1 前序遍历

2.2 中序遍历

2.3 后序遍历

2.4 层序遍历

3. 二叉树基本操作

3.1 求树的所有结点个数

3.2 求叶子结点个数

3.3 求第k层结点个数

3.4 求二叉树的高度

3.5 检测树中是否存在值为val的结点

3.5 判断树是否为完全二叉树

4. 二叉树相关OJ题

4.1 相同的树

4.2 另一棵树的子树

4.3 翻转二叉树

4.4 二叉树的最大深度

4.5 平衡二叉树

4.6 对称二叉树

4.7 二叉树创建及遍历

4.8 二叉树的层序遍历

4.9 二叉树的最近公共祖先

4.10 已知中序与前序遍历构造二叉树

4.11 已知中序与后序遍历构造二叉树

4.12 根据二叉树创建字符串

4.13 二叉树的前序遍历(递归与非递归)

4.14 二叉树的中序遍历(递归与非递归)

4.15 二叉树的后序遍历(递归与非递归)