最近做二叉树的题目，写完代码想在本地编译运行，结果一时半会想不起树如何构造。而网上竟然也没有类似代码，于是自己写了个。
 
约定：二叉树采用宽度优先遍历来数组化，二叉树的节点按照BFS的顺序依次存储在数组内，数组中的’#’代表空节点，末尾的’#’可省略。 
 如：
 
    1
   / \
  2   3
 / \   \
4   5   6
   / \
  7   8
 
这棵树会被序列化为：{1,2,3,4,5,#,6,#,#,7,8}，后面的四个#被省略。
 
          7
       /    \
    2         8
  /   \        \
 1    6        10
      /       /  \
     3        9   11
       \
       5
      /
     4
//数组应该为{7,2,8,1,6,#,10,#,#,3,#,#,#,9,11,#,#,#,#,#,5,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,#,4}
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//二叉树的节点定义
class TreeNode {
     public:
         int val;
         TreeNode *left, *right;
         TreeNode(int val) {
             this->val = val;
             this->left = this->right = NULL;
         }
};

//从数组的某个位置的元素开始生成树
TreeNode* createTree(vector<int> list, int start){

    if (list[start] == '#') {
        return NULL;
    }

    TreeNode* root = new TreeNode(list[start]);

    int lnode = 2*start + 1;
    int rnode = 2*start + 2;
    if ( lnode > list.size() -1) {
        root -> left = NULL;
    }else{
        root -> left = createTree(list, lnode);
    }

    if (rnode > list.size() -1) {
        root -> right =NULL;
    }else{
        root -> right = createTree(list, rnode);
    }

    return root;
}

//先序遍历函数
void PreOrderTraverse(TreeNode *T)                
{
    if(T)
    {
        cout<<T->val<<" ";                
        PreOrderTraverse(T->left);           
        PreOrderTraverse(T->right);           
    }
    return;
}


int main()
{
    vector<int> datanum = {1,2,3,4,5,'#',6,'#','#',7,8};
    //1,2,3,4,5,'#',6,'#','#',7,8,'#','#','#','#' 后面的#可省略
    TreeNode *t;
    t = createTree(datanum, 0);

    printf("The pre order is : ");
    PreOrderTraverse(t);

    //下面就可以用构造出的树做测试了

    return 0;
}

二叉树是每个节点最多有两个子树的树结构。通常子树被称作 “左子树” 和 “右子树”。
 
比如数组：
 int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9}

 变为二叉树为：
 
 
 
 
分析：
 
1、首先要定义每一个结点，每一个结点包括自身值，左结点和右结点，实现get、set方法。
 
public class Node {
      public int data;      //自己本身值
      public Node left;     //左结点
      public Node right;     //右结点
      public Node() {
      }
      public Node(int data, Node left, Node right) {
           this.data = data;
           this.left = left;
           this.right = right;
      }
      public int getData() {
          return data;
      }
      public void setData(int data) {
          this.data = data;
      }
      public Node getLeft() {
          return left;
      }
      public void setLeft(Node left) {
          this.left = left;
      }
      public Node getRight() {
          return right;
      }
      public void setRight(Node right) {
          this.right = right;
      }
 }
 
2、创建二叉树
 
public class Demo2 {
     public static List<Node> list = new ArrayList<Node>();      //用一个集合来存放每一个Node
     public void createTree(int[] array) {
     for (int i = 0; i < array.length; i++) {
          Node node = new Node(array[i], null, null);    //创建结点，每一个结点的左结点和右结点为null
          list.add(node); // list中存着每一个结点
     }
     // 构建二叉树
     if (list.size() > 0) {
         for (int i = 0; i < array.length / 2 - 1; i++) {       // i表示的是根节点的索引，从0开始
              if (list.get(2 * i + 1) != null) { 
                   // 左结点
                   list.get(i).left = list.get(2 * i + 1);
              }
              if (list.get(2 * i + 2) != null) {
                   // 右结点
                   list.get(i).right = list.get(2 * i + 2);
              }
        }
        // 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理
        int lastIndex = array.length / 2 - 1;
        // 左结点
        list.get(lastIndex).left = list.get(lastIndex * 2 + 1);
        // 右结点，如果数组的长度为奇数才有右结点
        if (array.length % 2 == 1) {
             list.get(lastIndex).right = list.get(lastIndex * 2 + 2);
        }
    }
 }
 
// 遍历，先序遍历
 public static void print(Node node) {
      if (node != null) {
            System.out.print(node.data + " ");
            print(node.left);
            print(node.right);
      }
 }
 
   public static void main(String[] args) {
         int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
         Demo2 demo = new Demo2();
         demo.createTree(array);
         print(list.get(0));
   }
 }
 
结果为：
 
1 2 4 8 9 5 3 6 7 
 
 
 
分析:
 
array = {1, 2, 3, 4, 5, 6, 7, 8, 9}
 lastIndex = 3;
 i=0
 1
 2 3
 i=1
 2
 4 5
 i=2
 3
 6 7
 
         1
       2     3
      4 5   6 7
  
 
lastIndex=3
 4
 8 9
 
 
 
         1
       2     3
      4 5   6 7
     8 9

把有序数组转换为平衡二叉树。
<pre name="code" class="cpp">TreeNode* buildTree(vector<int> &nums,int start,int last)
{
	int mid = (start + last) / 2;
	TreeNode *root = new TreeNode(nums[mid]);
	if(start == last)
	{
		return root;
	}
	if(start <= mid - 1)
	{
		root->left = buildTree(nums,start,mid-1);
	}
	if(mid+1 <=  last)
	{
		root->right = buildTree(nums,mid+1,last);
	}
	return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
	if(nums.empty())
		return NULL;
	return buildTree(nums,0,nums.size()-1);
}
 
 

请实现两个函数，分别用来序列化和反序列化二叉树。

示例: 

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"
注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    public StringBuilder rserialize(TreeNode root, StringBuilder sb){
        if(root == null) sb.append("null,");
        else {
            sb.append(root.val);
            sb.append(",");

            rserialize(root.left, sb);
            rserialize(root.right, sb);
        }
        return sb;
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return rserialize(root, new StringBuilder()).toString();
    }

    public TreeNode rdeserialize(ArrayList<String> list) {
        String s = list.remove(0);
        TreeNode root = null;
        if(!s.equals("null")){
            root = new TreeNode(Integer.parseInt(s));
            root.left = rdeserialize(list);
            root.right = rdeserialize(list);
        }
        return root;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] parts = data.split(",");
        ArrayList<String> list = new ArrayList<>(Arrays.asList(parts));
        return rdeserialize(list);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));