【Java -- 算法】分治算法

一、简介

今天这篇文章，介绍一下和二叉树有关的操作，所有代码均可通过 菜鸟工具在线编译器 直接运行，因此打算整理一下分享给大家。

这部分包括：

• 获得二叉树的镜像
• 判断元素是否存在于二叉树中
• 打印二叉树中和为s的路径
• 获得二叉树的最大距离
• 判断二叉树是否是平衡树

二、代码实现 获得二叉树的镜像

1. 代码实现

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i  value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i > 5 is in tree=true
>> 9 is in tree=false

打印二叉树中和为 s 的路径

1. 问题描述

输入一个整数和一棵二叉树，打印出和与输入整数相等的所有路径，从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

2. 代码实现

import java.util.LinkedList;

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i  value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i  rightDepth ? leftDepth + 1 : rightDepth + 1;
        //(1) 通过根结点，则选取左子树的深度+右子树深度+2
        int throughRoot = leftDepth + rightDepth + 2;
        //(2) 不通过根结点，则选取左右子树的距离最大值。
        int notThroughRoot = leftDistance > rightDistance ? leftDistance : rightDistance;
        //取以上两者的最大值，作为该结点的最大距离属性。
        node.maxDistance = throughRoot > notThroughRoot ? throughRoot : notThroughRoot;
    }

    static void printInOrder(Node node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        //遍历完左子树后，打印根结点，最后遍历右子树。
        System.out.println("value=" + node.value + ", depth=" + node.maxDepth + ", distance=" + node.maxDistance);
        printInOrder(node.right);
    }

    public static void main(String[] args) {
        int p[] = {3, 5, 6, 1, 2, 4, -1, -3};
        Tree tree = createBinTree(p, p.length);
        calculateMaxTreeDistance(tree.root);
        System.out.println("最大距离=" + tree.root.maxDistance);
    }
}

3. 运行结果

>> 最大距离=6

判断二叉树是否是平衡树

1. 问题描述

平衡二叉树 具有以下性质：它是一棵空树或它的 左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

2. 解决思路

根据平衡二叉树的定义，对于每个结点需要满足两个条件：

• 左右子树都是平衡树
• 左右子树的高度差小于等于1

因此，我们可以采用递归的方式来实现，对于每个结点，返回一个数据结构BalanceValue表示以该结点为根结点的子树是否是平衡树，以及它的高度（叶结点的高度为0）。

3. 代码实现

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static class BalanceValue {
        boolean isBalance;
        int treeHeight;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入结点的父结点，如果遍历完为空，说明此时是一个空树。
        Node pNode = null;
        //新的结点。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i = 0; i > 平衡树=false