[数据结构] 二叉树题目 (二)

目录

一. 另一颗树的子树

1.1 题目

1.2 示例

1.3 分析

1.4 解决

二. 平衡二叉树

2.1 题目

2.2 示例

2.3 分析

2.4 解决

三. 二叉树的遍历和创建

3.1 题目

3.2 示例

3.3 解决

一. 另一颗树的子树572. 另一棵树的子树 - 力扣（LeetCode）

1.1 题目

1.2 示例

1.3 分析

遍历root树, 找到与subRoot树起始节点数值相等的节点. 之后再判断以这个节点起始的子树是否与subRoot相同.

1.4 解决

二. 平衡二叉树110. 平衡二叉树 - 力扣（LeetCode）

2.1 题目

2.2 示例

2.3 分析

平衡二叉树: 每个节点的左右子树的高度差 <= 1.

前序遍历每个节点, 再分别求出每个节点左右子树的高度, 最后做差判断是否符合条件.

2.4 解决

三. 二叉树的遍历和创建二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

3.1 题目

3.2 示例

3.3 解决

import java.util.Scanner;
class TreeNode {
    char ch;
    TreeNode left;
    TreeNode right;
    TreeNode(char ch) {
        this.ch = ch;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String string = in.next();
            // System.out.println(string);
            // 创建二叉树
            TreeNode root = createTree(string);
            // 中序遍历
            inorderTree(root);
        }
    }
    public static int i = 0;
    public static TreeNode createTree(String string) {
        if (i == string.length()) return null;
        TreeNode root = null;
        if (string.charAt(i) == '#') {
            i++;
        } else {
            root = new TreeNode(string.charAt(i));
            i++;
            root.left = createTree(string);
            root.right = createTree(string);

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