【Java -- 算法】动态规划算法

一、简介

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

这部分包括：

• 将二叉树转换成为链表
• 判断数组是否为二叉树的后序遍历
• 判断某树是否是另一棵树的子树
• 根据前序和中序序列重建二叉树

二、代码实现 将二叉树转换成为链表

1. 解决思路

采用后序遍历的思路，先将左右子树转换成链表，再将左右子树的链表通过中间结点连接起来。

2. 代码实现

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

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

    static class ListValue {
        Node header;
        Node tail;
    }

    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 > p2 是二叉查找树的后序遍历=false

判断某树是否是另一棵树的子树

1. 解决思路

先判断父树和子树的根结点是否相等，如果相等，再比较两棵树是否完全相同，如果根结点不相等，那么再递归比较父树的左子树和子树，以及父树的右子树和子树。

2. 代码实现

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 > p2 是 p1 的子树=true
>> p3 是 p1 的子树=false

根据先序遍历和中序遍历重建二叉树

1. 解决思路

根据先序遍历的特点，其第一个元素为树的根结点，然后在中序遍历的结点中找到该根结点，分为左右两个子树部分，递归进行求解。

2. 代码实现

public class Untitled {

    static class Tree {
        int size;
        Node root;
    }

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

    static Node createTree(int preOrder[], int preStart, int preEnd, int inOrder[], int inStart, int inEnd) {
        Node node = new Node();
        int root = preOrder[preStart];
        node.value = root;
        //如果只有一个元素，那么直接返回即可。
        if (preStart == preEnd) {
            return node;
        }
        int rootIndex = inStart;
        while (rootIndex