重建二叉树

知识回顾

二叉树

• 先序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根

TreeNode

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

注：这是c的结构体，而JAVA用class去表示

复制该网页的代码进行学习
该代码的结构是

1. 有一个类Tree，Tree里
   1存放的是根结点
   2还有一个名叫list的容器，存放node
   3一个初始化函数——把所有的节点都放了进去（从叶子节点开始初始化是这个函数的灵魂）

2. 有一个private类Node。
   1存放节点的数值
   2以及它指向的左孩子、右孩子

3. 三序遍历的方式使用函数preOrder、inOrder、postOder（它们的灵魂则是采用递归的方式）

preOrder
1函数先把根节点放了进去
2然后从左开始找下一个根节点
3如果左边没有那就把右作为根的根节点

inOrder
1先找到最左的节点
2先执行.lchild最深的递归，执行完这一层，然后不断往前移

笔记

import java.util.ArrayList;  
import java.util.List;  
  
public class Tree {  
    private Node root;  
    private List<Node> list=new ArrayList<Node>();  
    public Tree(){  
        init();  
    }  
    //树的初始化:先从叶节点开始,由叶到根  
    public void init(){  
        Node x=new Node("X",null,null);  
        Node y=new Node("Y",null,null);  
        Node d=new Node("d",x,y);  
        Node e=new Node("e",null,null);  
        Node f=new Node("f",null,null);  
        Node c=new Node("c",e,f);  
        Node b=new Node("b",d,null);  
        Node a=new Node("a",b,c);  
        root =a;  
    }  
    //定义节点类：  
    private class Node{  
      private String data;  
      private Node lchid;//定义指向左子树的指针  
      private Node rchild;//定义指向右子树的指针  
      public Node(String data,Node lchild,Node rchild){  
          this.data=data;  
          this.lchid=lchild;  
          this.rchild=rchild;  
      }  
    }  
  
    /** 
      * 对该二叉树进行前序遍历 结果存储到list中 前序遍历:ABDXYCEF 
      */  
     public void preOrder(Node node)  
     {  
  
            list.add(node); //先将根节点存入list  
            //如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点  
            if(node.lchid != null)  
            {  
                preOrder(node.lchid);  
            }  
            //无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序  
            if(node.rchild != null)  
            {  
                preOrder(node.rchild);  
            }  
     }  
  
     /** 
      * 对该二叉树进行中序遍历 结果存储到list中，中序结果XdYbaecf 
      */  
     public void inOrder(Node node)  
     {  
        if(node.lchid!=null){  
            inOrder(node.lchid);  
        }  
        list.add(node);  
        if(node.rchild!=null){  
            inOrder(node.rchild);  
        }  
     }  
  
     /** 
      * 对该二叉树进行后序遍历 结果存储到list中，后续结果：XYdbefca 
      */  
     public void postOrder(Node node)  
     {  
         if(node.lchid!=null){  
             postOrder(node.lchid);  
         }  
         if(node.rchild!=null){  
             postOrder(node.rchild);  
         }  
         list.add(node);  
  
     }  
  
     /** 
      * 返回当前数的深度 
      *  说明: 
      *  1、如果一棵树只有一个结点，它的深度为1。 
      *  2、如果根结点只有左子树而没有右子树，那么树的深度是其左子树的深度加1； 
      *  3、如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1； 
      *  4、如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。 
      *   
      * @return 
      */  
     public int getTreeDepth(Node node) {  
  
            if(node.lchid == null && node.rchild == null)  
            {  
                return 1;  
            }  
            int left=0,right = 0;  
            if(node.lchid!=null)  
            {  
                left = getTreeDepth(node.lchid);  
            }  
            if(node.rchild!=null)  
            {  
                right = getTreeDepth(node.rchild);  
            }  
            return left>right?left+1:right+1;  
        }  
  
  
    //得到遍历结果  
     public List<Node> getResult()  
     {  
      return list;  
     }  
  
     public static void main(String[] args) {  
        Tree tree=new Tree();  
        System.out.println("根节点是:"+tree.root);  
        //tree.preOrder(tree.root);  
        tree.postOrder(tree.root);  
        for(Node node:tree.getResult()){  
            System.out.println(node.data);  
        }  
        System.out.println("树的深度是"+tree.getTreeDepth(tree.root));  
  
    }   
  
}  

以上二叉树会被序列化为 {1,2,3,#,#,4,#,#,5}
1：root节点1，是第一层
2,3：然后第二层是2，3
#,#,4,#：第三层分别是2节点的两个孩子节点空，用#来表示，然后3节点的左孩子为4，右孩子节点为#
#,5：第四层4节点的左孩子是空，右孩子为5
最后一层5节点的两个空孩子不遍历

创建对象数组