• 【算法】二叉树

    1.二叉搜索树的范围和(938-java)

    给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

    示例 1：

    img

    输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
    输出：32

    public class LC249_938_rangeSumBST {
    //二叉树
    static int sum = 0;

    public static int rangeSumBST(TreeNode root, int low, int high) {
        //二叉树的中序遍历
        if (root == null) {
            return 0;
        }
        //判断大小情况
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }

        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        //返回最终结果
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        int i = rangeSumBST(tree, 2, 15);
        System.out.println(i);
    }

}

    • 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

    2.开幕式焰火(lcp-44-java)

    「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。
    给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。

    示例 1：

    输入：root = [1,3,2,1,null,2]

    输出：3

    解释：焰火中有 3 个不同的颜色，值分别为 1、2、3

    示例 2：

    输入：root = [3,3,3]

    输出：1

    解释：焰火中仅出现 1 个颜色，值为 3

    public class LC250_lcp_44_numColor {
    //二叉树--前序遍历--先访问根节点
    static Set<Integer> set = new HashSet<>();

    public static int numColor(TreeNode root) {
        if (root == null) {
            return 0;
        }
        set.add(root.val);
        numColor(root.left);
        numColor(root.right);
        return set.size();
    }

    public static void main(String[] args) {
        int i = numColor(TreeNode.createTree());
        System.out.println(i);
    }

}

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

    3.翻转二叉树(226-java)

    考察:递归使用

    给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

    示例 1：

    输入：root = [4,2,7,1,3,6,9]
    输出：[4,7,2,9,6,3,1] > [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lrd6A1q1-1659079341302)(https://s2.loli.net/2022/07/29/Iea9QT6My4WdOpn.jpg)]

    public class LC009_226_invertTree {
    //递归解法
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //暂存left节点
        TreeNode left = root.left;
        //右边赋值到左边
        root.left = root.right;
        //左边赋值到右边
        root.right = left;
        //递归其他节点
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        TreeNode.printTree(root);
        System.out.println();
        TreeNode treeNode = invertTree(root);
        TreeNode.printTree(treeNode);
    }
}

    • 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.合并二叉树(617-go-java)

    给你两棵二叉树： root1 和 root2 。

    想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

    返回合并后的二叉树。

    注意: 合并过程必须从两个树的根节点开始。

    img

    示例 1：

    输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
    输出：[3,4,5,5,4,null,7]

    /
func mergeTreesSelf(t1 *TreeNode, t2 *TreeNode) *TreeNode {
    //以t1为中心
    if t1 == nil&&t2!=nil {
        return t2
    }
    if (t1!=nil&&t2 == nil)|| (t1==nil&&t2 == nil){
        return t1
    }
    t1.val+=t2.val
    t1.left=mergeTreesSelf(t1.left,t2.left)
    t1.right=mergeTreesSelf(t1.right,t2.right)
    return t1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    public class LC251_617_mergeTrees {
    //二叉树--前序遍历
    public static TreeNode mergeTrees(TreeNode r1, TreeNode r2) {

        if (r1 == null && r2 == null) {
            return null;
        }
        if (r1 == null) {
            return r2;
        }
        if (r2 == null) {
            return r1;
        }
        r1.val += r2.val;
        r1.left = mergeTrees(r1.left, r2.left);
        r1.right = mergeTrees(r1.right, r2.right);
        return r1;
    }

    public static void main(String[] args) {
        TreeNode treeNode = mergeTrees(TreeNode.createTree(), TreeNode.createTree());
        TreeNode.printTree(treeNode);
    }

}

    • 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
    public static TreeNode mergeTrees_timian(TreeNode r1, TreeNode r2) {
        if (r1 == null) {
            return r2;
        }
        if (r2 == null) {
            return r1;
        }
        //假设返回r1
        r1.val += r2.val;
        r1.left = mergeTrees_timian(r1.left, r2.left);
        r1.right = mergeTrees_timian(r1.right, r2.right);
        return r1;
    }

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

    5.二叉搜索树中的搜索(700-java)

    给定二叉搜索树（BST）的根节点和一个值。 你需要在 BST 中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

    例如，

    给定二叉搜索树:

    4
    / \

    2 7
    /
    1 3

    和值: 2
    你应该返回如下子树:

    2
    / \
    1 3

    public class LC252_700_searchBST {
    //二叉树---递归
    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        return root.val < val ? searchBST(root.right, val) : searchBST(root.left, val);
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        TreeNode treeNode = searchBST(tree, 3);
        TreeNode.printTree(treeNode);
    }
}

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

    6.二叉树的最大深度(104-java)

    考察:

    • 递归
    • 层序遍历

    给定一个二叉树，找出其最大深度。

    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

    说明: 叶子节点是指没有子节点的节点。

    示例：
    给定二叉树 [3,9,20,null,null,15,7]，

    3
    /
    9 20
    /
    15 7
    返回它的最大深度 3 。

    public class LC017_104_maxDepth {
    //递归 dfs  时间复杂度O(n)  空间复杂度:线性表最差O(n)、二叉树完全平衡最好O(logn)
    public static 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;
    }

    //层序遍历
    public static int maxDept2(TreeNode root) {
        int ans = 0;
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode poll = queue.poll();
                TreeNode left = poll.left;
                TreeNode right = poll.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.generateRandomBST(1, 1000, 3);
        TreeNode.printTree(node);
        System.out.println(maxDept2(node));
        //TreeNode.printTree(node);
    }
}

    • 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

    7.将有序数组转换为二叉搜索树(108-java)

    给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

    高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

    示例 1：

    img

    输入：nums = [-10,-3,0,5,9]
    输出：[0,-3,9,-10,null,5]
    解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

    img

    public class LC166_108_sortedArrayToBST {
    //递归
    public static TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private static TreeNode dfs(int[] nums, int low, int high) {
        if (low > high) {
            return null;
        }
        int mid = low + (high - low) / 2;
        TreeNode treeNode = new TreeNode(nums[mid]);
        treeNode.left = dfs(nums, low, mid - 1);
        treeNode.right = dfs(nums, mid + 1, high);
        return treeNode;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-10, -3, 0, 5, 9};
        TreeNode treeNode = sortedArrayToBST(nums);
        TreeNode.printTree(treeNode);
    }
}

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

    8.二叉树的中序遍历(94-java)

    给定一个二叉树的根节点 root ，返回它的 中序 遍历。

    示例 1：

    img

    输入：root = [1,null,2,3]
输出：[1,3,2]

    • 1
    • 2
    public class LC48_94_inorderTraversal {

    static List<Integer> res = new ArrayList<>();

    //递归中序遍历+递归
    public static List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }
        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);
        return res;
    }

    //迭代
    public static List<Integer> inorderTraversal111(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (stack.size() > 0 || root != null) {
            //不断往左子树方向走，每走一次就将当前节点保存到栈中
            //这是模拟递归的调用
            if (root != null) {
                stack.add(root);
                root = root.left;
                //当前节点为空，说明左边走到头了，从栈中弹出节点并保存
                //然后转向右边节点，继续上面整个过程
            } else {
                TreeNode node = stack.pop();
                res.add(node.val);
                root = node.right;
            }
        }
        return res;
    }

    //morris遍历
    public static void inOrderMorris(TreeNode head) {
        if (head == null) {
            return;
        }
        TreeNode cur1 = head;
        TreeNode cur2 = null;
        while (cur1 != null) {
            cur2 = cur1.left;
            //构建连接线
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                } else {
                    cur2.right = null;
                }
            }
            res.add(cur1.val);
            cur1 = cur1.right;
        }
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.createTree();
        TreeNode.printTree(node);
        List<Integer> integers = inorderTraversal(node);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}

    • 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
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71

    9.二叉树的后序遍历(145-java)

    给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

    示例 1：

    img

    输入：root = [1,null,2,3]
    输出：[3,2,1]
    示例 2：

    输入：root = []
    输出：[]

    public class LC99_145_postorderTraversal {
    static List<Integer> res = new ArrayList<>();

    //递归
    public static List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        res.add(root.val);
        return res;
    }

    //迭代法
    public static List<Integer> postorderTraversal1111(TreeNode root) {
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        Collections.reverse(res);//可以用2个栈
        return res;
    }

    //后序Morris
    public static List<Integer> postOrderMorris(TreeNode head) {
        if (head == null) {
            return res;
        }
        TreeNode cur1 = head;//遍历树的指针变量
        TreeNode cur2 = null;//当前子树的最右节点
        while (cur1 != null) {
            cur2 = cur1.left;
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                } else {
                    cur2.right = null;
                    postMorrisPrint(cur1.left);
                }
            }
            cur1 = cur1.right;
        }
        postMorrisPrint(head);
        return res;
    }

    //打印函数
    public static void postMorrisPrint(TreeNode head) {
        TreeNode reverseList = postMorrisReverseList(head);
        TreeNode cur = reverseList;
        while (cur != null) {
            res.add(cur.val);
            cur = cur.right;
        }
        postMorrisReverseList(reverseList);
    }

    //翻转单链表
    public static TreeNode postMorrisReverseList(TreeNode head) {
        TreeNode cur = head;
        TreeNode pre = null;
        while (cur != null) {
            TreeNode next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.createTree();
        TreeNode.printTree(node);
        List<Integer> integers = postOrderMorris(node);
        for (Integer integer : integers) {
            System.out.print(integer + " ");
        }
    }
}

    • 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
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96

    10.递增顺序搜索树(897-java)

    给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

    示例 1：

    img

    输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
    输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

    public class LC253_897_increasingBST {
    //二叉树--中序遍历
    static List<TreeNode> list = new ArrayList<>();

    public static TreeNode increasingBST(TreeNode root) {
        dfs(root);
        //递归
        TreeNode dummy = new TreeNode(-1);
        TreeNode curr = dummy;
        for (TreeNode node : list) {
            node.left = null;
            curr.right = node;
            curr = node;
        }
        return dummy.right;
    }

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        list.add(root);
        dfs(root.right);
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode treeNode = increasingBST(tree);
        TreeNode.printTree(treeNode);
    }
}

    • 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

    11.从根到叶的二进制数之和(1022-java)

    给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。

    对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

    返回这些数字之和。题目数据保证答案是一个 32 位 整数。

    示例 1：

    img

    输入：root = [1,0,1,0,1,0,1]
    输出：22
    解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
    示例 2：

    输入：root = [0]
    输出：0
    示例 3：

    输入：root = [1]
    输出：1

    public class LC254_1022_sumRootToLeaf {
    //二叉树
    static int ans = 0;
    public static int sumRootToLeaf(TreeNode root) {
        sum(root, 0);
        return ans;
    }
    private static void sum(TreeNode root, int i) {
        if (root == null) {
            return;
        }
        int val = i * 2 + root.val;
        if (root.left == null && root.right == null) {
            ans += val;
            return;
        }
        sum(root.left, val);
        sum(root.right, val);
    }
    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        System.out.println(sumRootToLeaf(tree));
    }
}

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

    12.二叉树的前序遍历(144-java)

    给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

    示例 1：

    img

    输入：root = [1,null,2,3]
输出：[1,2,3]

    • 1
    • 2
    public class LC74_144_preorderTraversal {
    static List<Integer> res = new ArrayList<>();

    //递归
    public static List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    }

    //迭代
    public static List<Integer> preorderTraversal222(TreeNode root) {
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            //栈是先进后出的结构
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }

    //morris
    public static List<Integer> preorderTraversalMorris(TreeNode root) {
        if (root == null) {
            return res;
        }
        TreeNode cur1 = root;
        TreeNode cur2;
        while (cur1 != null) {
            cur2 = cur1.left;
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    cur2.right = cur1;
                    res.add(cur1.val);
                    cur1 = cur1.left;
                    continue;
                } else {
                    cur2.right = null;
                }
            } else {
                res.add(cur1.val);
            }
            cur1 = cur1.right;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        TreeNode.printTree(root);
        System.out.println();
        List<Integer> integers = preorderTraversalMorris(root);
        for (Integer integer : integers) {
            System.out.print(integer + " ");
        }
    }
}

    • 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
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    13.二叉树的层平均值(637-java)

    给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

    示例 1：

    输入：
    3
    /
    9 20
    /
    15 7
    输出：[3, 14.5, 11]
    解释：
    第 0 层的平均值是 3 , 第 1 层是 14.5 , 第 2 层是 11 。因此返回 [3, 14.5, 11] 。

    public class LC255_637_averageOfLevels {
    //二叉树--广度优先--bfs
    public static List<Double> averageOfLevels(TreeNode root) {

        //1.定义结果集
        List<Double> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        //2.定义queue
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //3.遍历
        while (!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0;
            int i = -1;
            while (++i < size) {
                TreeNode poll = queue.poll();
                sum += poll.val;
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            ans.add(sum / size);
        }
        return ans;
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        List<Double> doubles = averageOfLevels(tree);
        for (Double aDouble : doubles) {
            System.out.println(aDouble);
        }
    }
}

    • 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

    14.二叉树的所有路径(257-java)

    给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

    叶子节点 是指没有子节点的节点。

    示例 1：img

    输入：root = [1,2,3,null,5]
    输出：[“1->2->5”,“1->3”]

    public class LC171_257_binaryTreePaths {
    //回溯
    public static List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<String> path = new LinkedList<>();
        dfs(root, path, res);
        return res;
    }

    private static void dfs(TreeNode root, Deque<String> path, List<String> res) {
        if (root == null) {
            return;
        }
        path.add(String.valueOf(root.val));
        if (root.left == null && root.right == null) {
            res.add(String.join("->", path));
        }
        dfs(root.left, path, res);
        dfs(root.right, path, res);
        path.removeLast();
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.createTree();
        List<String> strings = binaryTreePaths(root);
        for (String string : strings) {
            System.out.print(string + " ");
        }
    }
}

    • 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

    15.单值二叉树(965-java)

    如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

    只有给定的树是单值二叉树时，才返回 true；否则返回 false。

    示例 1：img

    输入：[1,1,1,1,1,null,1]
    输出：true

    public class LC256_965_isUnivalTree {
    //二叉树---dfs
    static boolean flag = true;

    public static boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        dfs(root, root.val);
        return flag;
    }

    private static void dfs(TreeNode root, int val) {
        if (root == null) {
            return;
        }
        if (root.val != val) {
            flag = false;
            return;
        }
        dfs(root.left, val);
        dfs(root.right, val);
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        System.out.println(isUnivalTree(tree));
    }
}

    • 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

    16.二叉搜索树的最近公共祖先(235-java)

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

    百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

    例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

    img

    示例 1:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6
    解释: 节点 2 和节点 8 的最近公共祖先是 6。

    public class LC181_235_lowestCommonAncestor {
    //二叉树的特性
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

}

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

    17.二叉树的坡度(563-java)

    给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。

    一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。

    整个树 的坡度就是其所有节点的坡度之和。

    示例 1：

    img

    输入：root = [1,2,3]
    输出：1
    解释：
    节点 2 的坡度：|0-0| = 0（没有子节点）
    节点 3 的坡度：|0-0| = 0（没有子节点）
    节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
    坡度总和：0 + 0 + 1 = 1

        //二叉树
    static int ans = 0;

    public static int findTilt(TreeNode root) {
        //递归
        //计算子树坡度
        //计算子树权值和
        if (root == null) {
            return 0;
        }
        dfs(root);
        return ans;
    }

    private static int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        ans += Math.abs(left - right);
        return left + right + root.val;
    }

    public static void main(String[] args) {
        int tilt = findTilt(TreeNode.createTree());
        System.out.println(tilt);
    }
}

    • 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

    18.叶子相似的树(872-java)

    请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

    举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

    如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

    如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

    示例 1：img

    img

    输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
    输出：true

    public class LC258_872_leafSimilar {
    //二叉树
    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        //list集合
        //存储叶子结点
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        if (list1.size() == list2.size()) {
            for (int i = 0; i < list1.size(); i++) {
                if (!list1.get(i).equals(list2.get(i))) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    private static void dfs(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        dfs(root.left, list);
        dfs(root.right, list);
    }

    public static void main(String[] args) {
        boolean b = leafSimilar(TreeNode.createTree(), TreeNode.createTree());
        System.out.println(b);
    }
}

    • 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

    19.二叉搜索树的最小绝对差(530-java)

    给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

    差值是一个正数，其数值等于两值之差的绝对值。

    示例 1：img

    输入：root = [4,2,6,1,3]
    输出：1

    public class LC259_530_getMinimumDifference {
    //二叉树
    static int ans = Integer.MAX_VALUE;
    static TreeNode pre;

    public static int getMinimumDifference(TreeNode root) {
        //中序遍历
        if (root == null) {
            return 0;
        }
        dfs(root);
        return ans;
    }

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre != null) {
            ans = Math.min(ans, root.val - pre.val);
        }
        pre = root;
        dfs(root.right);
    }

    public static void main(String[] args) {
        System.out.println(getMinimumDifference(TreeNode.createTree()));
    }
}

    • 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

    20.两数之和 IV - 输入 BST(653-java)

    给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

    示例 1：

    img

    输入: root = [5,3,6,2,4,null,7], k = 9
    输出: true

    public class LC260_653_findTarget {
    //二叉树
    static List<Integer> tmp = new ArrayList<>();

    public static boolean findTarget(TreeNode root, int k) {
        dfs(root);
        int left = 0, right = tmp.size() - 1;
        while (left < right) {
            if ((tmp.get(left) + tmp.get(right)) == k) {
                return true;
            } else if ((tmp.get(left) + tmp.get(right)) > k) {
                right--;
            } else if ((tmp.get(left) + tmp.get(right)) < k) {
                left++;
            }
        }
        return false;
    }

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        tmp.add(root.val);
        dfs(root.right);
    }

    public static void main(String[] args) {
        boolean target = findTarget(TreeNode.createTree(), 3);
        System.out.println(target);
    }
}

    • 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

    21.相同的树(100-java)

    给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

    如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

    示例 1：img

    输入：p = [1,2,3], q = [1,2,3]
    输出：true

    public class LC67_100_isSameTree {
    //递归
    public static 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);
    }
    public static void main(String[] args) {
        TreeNode p = TreeNode.createTree();
        TreeNode q=TreeNode.createTree();
        System.out.println(isSameTree(p, q));
    }
}

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

    22.左叶子之和(173-go-java)

    计算给定二叉树的所有左叶子之和。

        3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    func sumOfLeftLeavesSelf(root *TreeNode) int {
    var res int
    sumLeft(root, &res)
    return res
}
func sumLeft(root *TreeNode, res *int) {
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        *res += root.Left.Val
    }
    if root.Left != nil {
        sumLeft(root.Left, res)
    }
    if root.Right != nil {
        sumLeft(root.Right, res)
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    public class LC261_173_sumLeft {
    //二叉树
    static int ans = 0;

    public static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return ans;
        }
        dfs(root);
        return ans;
    }

    private static void dfs(TreeNode root) {
        if (root.left != null && root.left.left == null && root.left.right == null) {
            ans += root.left.val;
        }
        if (root.left != null) {
            dfs(root.left);
        }
        if (root.right != null) {
            dfs(root.right);
        }
    }

    public static void main(String[] args) {
        System.out.println(sumOfLeftLeaves(TreeNode.createTree()));
    }
}

    • 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

    23.二叉搜索树节点最小距离(783-java)

    给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

    差值是一个正数，其数值等于两值之差的绝对值。

    示例 1：img

    输入：root = [4,2,6,1,3]
    输出：1

    public class LC262_783_minDiffInBST {
    //二叉树
    static int ans = Integer.MAX_VALUE;
    static TreeNode pre;

    public static int minDiffInBST(TreeNode root) {
        //中序遍历
        if (root == null) {
            return 0;
        }
        dfs(root);
        return ans;
    }

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre != null) {
            ans = Math.min(ans, root.val - pre.val);
        }
        pre = root;
        dfs((root.right));
    }

    public static void main(String[] args) {
        System.out.println(minDiffInBST(TreeNode.createTree()));
    }
}

    • 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

    24.根据二叉树创建字符串(606-java)

    你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

    空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

    示例 1:

    输入: 二叉树: [1,2,3,4]
    1
    /
    2 3
    /
    4

    输出: “1(2(4))(3)”

    解释: 原本将是“1(2(4)())(3())”，
    在你省略所有不必要的空括号对之后，
    它将是“1(2(4))(3)”。

    public class LC263_606_tree2str {
    //二叉树  前序遍历
    public static String tree2str(TreeNode root) {
        //递归+前序遍历
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }

    private static void dfs(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        sb.append(root.val);
        if (root.left != null) {
            sb.append("(");
            dfs(root.left, sb);
            sb.append(")");
        }
        if (root.left == null && root.right != null) {
            sb.append("(");
            sb.append(")");
        }
        if (root.right != null) {
            sb.append("(");
            dfs(root.right, sb);
            sb.append(")");
        }
    }

    public static void main(String[] args) {
        String s = tree2str(TreeNode.createTree());
        System.out.println(s);
    }
}

    • 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

    25.对称二叉树(101-java)

    给你一个二叉树的根节点 root ， 检查它是否轴对称。

    示例 1：

    img

    输入：root = [1,2,2,3,4,4,3]
输出：true

    • 1
    • 2
    public class LC46_101_isSymmetric {
    //递归实现
    public static boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        return dfs自己(root.left, root.right);
    }

    static boolean dfs自己(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return dfs自己(left.left, right.right) && dfs自己(left.right, right.left);
    }

    //队列
    public static boolean isSymmetric队列(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        while (queue.size() > 0) {
            TreeNode left = queue.removeFirst();
            TreeNode right = queue.removeFirst();
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }
            queue.add(left.left);
            queue.add(right.left);
            queue.add(left.right);
            queue.add(right.left);
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.generateRandomBST(1, 100, 3);
        System.out.println(isSymmetric队列(node));
    }
}

    • 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

    26.平衡二叉树(110-java)

    给定一个二叉树，判断它是否是高度平衡的二叉树。

    本题中，一棵高度平衡二叉树定义为：

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

    示例 1：

    img

    输入：root = [3,9,20,null,null,15,7]
    输出：true

    public class LC104_110_isBalanced {
    //递归   自顶而下
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isBalanced(root.left) && isBalanced(root.right)
                && Math.abs(check(root.left) - check(root.right)) <= 1;
    }

    private static int check(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(check(root.left), check(root.right)) + 1;
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        System.out.println();
        System.out.println(isBalanced(tree));
    }

    public boolean isBalanced999(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 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

    27.二叉树的直径(543-java)

    给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

    示例 :
    给定二叉树

    1

    /
    2 3
    / \

    4 5
    返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

    注意：两结点之间的路径长度是以它们之间边的数目表示。

    public class LC139_543_diameterOfBinaryTree {

    static int max = 0;

    //递归--中序遍历--序是针对根节点
    public static int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        mid(root);
        return max;
    }

    private static int mid(TreeNode cur) {
        if (cur == null) {
            return 0;
        }
        int left = mid(cur.left);
        int right = mid(cur.right);
        max = Math.max(max, left + right);
        return 1 + Math.max(left, right);
    }


    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        System.out.println(diameterOfBinaryTree(tree));
    }

}

    • 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

    28.二叉树的堂兄弟节点(993-java)

    在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

    如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

    我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

    只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

    示例 1：

    img

    输入：root = [1,2,3,4], x = 4, y = 3
    输出：false

    public class LC264_993_isCousins {
    //二叉树
    public static boolean isCousins(TreeNode root, int x, int y) {
        //深度相同且父节点不同
        //递归
        //用数组存储结果集
        int[] dfs1 = dfs(root, null, 0, x);
        int[] dfs2 = dfs(root, null, 0, y);
        return dfs1[1] == dfs2[1] && dfs1[0] != dfs2[0];
    }

    private static int[] dfs(TreeNode root, TreeNode fa, int depth, int t) {
        if (root == null) {
            return new int[]{-1, -1};//搜索不到t
        }
        if (root.val == t) {
            return new int[]{fa != null ? fa.val : 1, depth};//父节点用1
        }
        int[] dfs = dfs(root.left, root, depth + 1, t);
        if (dfs[0] != -1) {
            return dfs;
        }
        return dfs(root.right, root, depth + 1, t);
    }

    public static void main(String[] args) {
        boolean cousins = isCousins(TreeNode.createTree(), 1, 2);
        System.out.println(cousins);
    }

}

    • 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

    29.路径总和(112-java)

    给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

    叶子节点 是指没有子节点的节点。

    示例 1：

    img

    输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    输出：true
    解释：等于目标和的根节点到叶节点路径如上图所示。

    public class LC84_112_hasPathSum {
    //递归
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.createTree();
        TreeNode.printTree(treeNode);
        System.out.println();
        System.out.println(hasPathSum(treeNode, 8));
    }

    public boolean hasPathSum9999(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == sum;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

    • 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.二叉搜索树中的众数(501-java)

    给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

    如果树中有不止一个众数，可以按 任意顺序 返回。

    假定 BST 满足如下定义：

    结点左子树中所含节点的值 小于等于 当前节点的值
    结点右子树中所含节点的值 大于等于 当前节点的值
    左子树和右子树都是二叉搜索树

    示例 1：

    img

    输入：root = [1,null,2,2]
    输出：[2]

    public class LC265_501_findMode {
    //二叉树
    static List<Integer> list = new ArrayList<>();
    static int preVal = 0;
    static int max = 1;
    static int count = 0;

    public static int[] findMode(TreeNode root) {
        dfs(root);
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private static void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        //中序遍历
        if (root.val == preVal) {
            count++;
        } else {
            preVal = root.val;
            count = 1;
        }
        if (count == max) {
            list.add(root.val);
        } else if (count > max) {
            list.clear();
            list.add(root.val);
            max = count;
        }
        dfs(root.right);
    }

    public static void main(String[] args) {
        int[] mode = findMode(TreeNode.createTree());
        for (int i : mode) {
            System.out.println(i);
        }
    }
}

    • 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

    31.数据流中的第 K 大元素(703-java)

    设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

    请实现 KthLargest 类：

    KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
    int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

    示例：

    输入：
    [“KthLargest”, “add”, “add”, “add”, “add”, “add”] > [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
    输出：
    [null, 4, 5, 5, 8, 8]

    解释：
    KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
    kthLargest.add(3); // return 4
    kthLargest.add(5); // return 5
    kthLargest.add(10); // return 5
    kthLargest.add(9); // return 8
    kthLargest.add(4); // return 8

    public class LC266_703_KthLargest {
    static PriorityQueue<Integer> queue;
    static int k = 0;

    public LC266_703_KthLargest(int k, int[] nums) {
        this.k = k;
        queue = new PriorityQueue<>(k);
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (queue.size() < k) {
            queue.offer(val);
        } else if (queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

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

    32.二叉树的最小深度(111-java)

    给定一个二叉树，找出其最小深度。

    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

    说明：叶子节点是指没有子节点的节点。

    示例 1：img

    输入：root = [3,9,20,null,null,15,7]
    输出：2

    public class LC75_111_minDepth {
    //递归--深度优先
    public static int minDepth(TreeNode root) {
        //最小深度,至少有一个叶子结点
        if (root == null) {
            return 0;
        }
        if ((root.left == null && root.right == null)) {
            return 1;
        }
        int min1 = minDepth(root.left);
        int min2 = minDepth(root.right);
        if ((root.left == null || root.right == null)) {
            return min1 + min2 + 1;
        }
        //加+1是因为根节点占一个深度
        return Math.min(min1, min2) + 1;
    }

    //广度优先
    public static int minDepth1111111(TreeNode root) {
        if (root == null) {
            return 0;
        }
        root.deep = 1;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.pop();
            if (node.left == null && node.right == null) {
                return node.deep;
            }
            if (node.left != null) {
                queue.offer(node.left);
                node.left.deep = node.deep + 1;
            }
            if (node.right != null) {
                queue.offer(node.right);
                node.right.deep = node.deep + 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        TreeNode node = TreeNode.createTree();
        TreeNode.printTree(node);
        int i = minDepth1111111(node);
        System.out.println(i);
    }

    public int minDepth99999(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //这道题递归条件里分为三种情况
        //1.左孩子和右孩子都为空的情况，说明到达了叶子节点，直接返回1即可
        if (root.left == null && root.right == null) {
            return 1;
        }
        //2.如果左孩子和右孩子其中一个为空，那么需要返回比较大的那个孩子的深度
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
        if (root.left == null || root.right == null) {
            return m1 + m2 + 1;
        }
        //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
        return Math.min(m1, m2) + 1;
    }

    //简化代码
    public int minDepth1111(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int m1 = minDepth1111(root.left);
        int m2 = minDepth1111(root.right);
        //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
        //2.如果都不为空，返回较小深度+1
        return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1, m2) + 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
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83

    33.二叉树中第二小的节点(671-java)

    给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

    更正式地说，root.val = min(root.left.val, root.right.val) 总成立。

    给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

    示例 1：img

    输入：root = [2,2,5,null,null,5,7]
    输出：5
    解释：最小的值是 2 ，第二小的值是 5 。

    public class LC267_671_findSecondMinimumValue {
    //二叉树
    static int result = -1;

    public static int findSecondMinimumValue(TreeNode root) {

        if (root == null) {
            return result;
        }
        dfs(root, root.val);
        return result;
    }

    private static void dfs(TreeNode root, int val) {
        if (root == null) {
            return;
        }
        if ((result == -1 && root.val > val) || (root.val > val && root.val < result)) {
            result = root.val;
        }
        dfs(root.left, val);
        dfs(root.right, val);
    }

    public static void main(String[] args) {
        int secondMinimumValue = findSecondMinimumValue(TreeNode.createTree());
        System.out.println(secondMinimumValue);
    }

}

    • 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

    34.另一棵树的子树(572-java)

    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

    示例 1：img

    输入：root = [3,4,5,1,2], subRoot = [4,1,2]
    输出：true

    public class LC268_572_isSubtree {
    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        //递归--传入2个treeNode
        return dfs(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private static boolean dfs(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        if (root.val != subRoot.val) {
            return false;
        }
        return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
    }

    public static void main(String[] args) {
        boolean subtree = isSubtree(TreeNode.createTree(), TreeNode.createTree());
        System.out.println(subtree);
    }

}

    • 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

    35.二叉搜索树中第 K 小的元素(剑指 offer-230-java)

    给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

    //方法一:中序遍历
public int kthSmallest(TreeNode root, int k) {
            Deque<TreeNode> deque = new ArrayDeque<>();
            while (root != null || !deque.isEmpty()) {
                while (root != null) {
                    deque.addLast(root);
                    root = root.left;
                }
                root = deque.pollLast();
                if (--k == 0) {
                    return root.val;
                }
                root = root.right;
            }
            return -1;
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    //方法二:  优先队列和栈
public int kthSmallest111(TreeNode root, int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.addLast(root);
    while (!deque.isEmpty()) {
        TreeNode treeNode = deque.pollFirst();
        if (queue.size() < k) {
            queue.add(treeNode.val);
        } else if (queue.peek() > treeNode.val) {
            queue.poll();
            queue.add(treeNode.val);
        }
        if (root.left != null) {
            deque.addLast(root.left);
        }
        if (root.right != null) {
            deque.addLast(root.right);
        }
    }
    return queue.peek();
}

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

    36.二叉搜索树迭代器(剑指 offer-055-java)

    实现一个二叉搜索树迭代器类 BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

    BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
    boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
    int next()将指针向右移动，然后返回指针处的数字。
    注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

    可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

    class BSTIterator {
    private TreeNode cur;
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new LinkedList<>();
    }

    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int ret = cur.val;
        cur = cur.right;
        return ret;
    }

    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }
}

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

    37.二叉树转为链表(114)

    考察

    1. 递归调用,左右分开
    2. 栈调用,迭代

    给你二叉树的根结点 root ，请你将它展开为一个单链表：

    • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
    public class LC007_114_flatten {
    //递归解法
    public static void flatten(TreeNode root) {
        //按图写代码
        if (root == null) {
            return;
        }
        //右子树暂存
        TreeNode rightTemp = root.right;
        flatten(root.left);
        root.right = root.left;
        root.left = null;
        //处理右边
        flatten(rightTemp);
        //寻找最右的节点
        while (root.right != null) {
            root = root.right;
        }
        root.right = rightTemp;
    }

    //栈解法
    public static void flatten2(TreeNode root) {
        //用栈实现
        TreeNode pre = null;
        TreeNode curr = root;
        Stack<TreeNode> stack = new Stack<>();
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.right;
            }
            curr = stack.peek();
            if (curr.left == null || curr.left == pre) {
                curr = stack.pop();
                curr.right = pre;
                curr.left = null;
                pre = curr;
                curr = null;
            } else {
                curr = curr.left;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        flatten2(tree);
        TreeNode.printTree(tree);
    }
}

    • 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
  • 相关阅读:
    两种基于时间窗口的限流器的简单实现
    STM32 LwIP学习过程问题总结（一）：LwIP ping不通，抓包发现ICMP校验和为0x0000
    210. 课程表 II
    Postman核心功能解析-参数化和测试报告
    看完这篇，还不懂JAVA内存模型(JMM)算我输
    微服务之流控、容错组件sentinel
    Jackson，Fastjson详细教程
    Filter过滤器
    【C语言】还搞不明白结构体吗？不妨来看看这篇文章，带你初步了解结构体
    Spring Cloud Gateway集成Swagger实现微服务接口文档统一管理及登录访问
  • 原文地址：https://blog.csdn.net/qyj19920704/article/details/126056804