449. 序列化和反序列化二叉搜索树

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

题解：
前言
二叉搜索树是一种特殊的二叉树，序列化和反序列化过程也可以参照「297. 二叉树的序列化与反序列化」的过程。二叉搜索树的特殊之处在于其中序遍历是有序的，可以利用这一点来优化时间和空间复杂度。

方法一：后序遍历
思路

给定一棵二叉树的「先序遍历」和「中序遍历」可以恢复这颗二叉树。给定一棵二叉树的「后序遍历」和「中序遍历」也可以恢复这颗二叉树。而对于二叉搜索树，给定「先序遍历」或者「后序遍历」，对其经过排序即可得到「中序遍历」。因此，仅对二叉搜索树做「先序遍历」或者「后序遍历」，即可达到序列化和反序列化的要求。此题解采用「后序遍历」的方法。

序列化时，只需要对二叉搜索树进行后序遍历，再将数组编码成字符串即可。

反序列化时，需要先将字符串解码成后序遍历的数组。在将后序遍历的数组恢复成二叉搜索树时，不需要先排序得到中序遍历的数组再根据中序和后序遍历的数组来恢复二叉树，而可以根据有序性直接由后序遍历的数组恢复二叉搜索树。后序遍历得到的数组中，根结点的值位于数组末尾，左子树的节点均小于根节点的值，右子树的节点均大于根节点的值，可以根据这些性质设计递归函数恢复二叉搜索树。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Codec {
  11.     public String serallize(TreeNode root) {
  12.         List<Integer> list = new ArrayList<Integer>();
  13.         postOrder(root,list);
  14.         String str = list.toString();
  15.         return str.substring(1,str.length()-1);
  16.     }
  18.     public TreeNode deserialize(String data) {
  19.         if (data.isEmpty()) {
  20.             return null;
  21.         }
  22.         String[] arr = data.split(",");
  23.         Deque<Integer> stack = new ArrayDeque<Integer>();
  24.         int length = arr.length;
  25.         for (int i = 0; i < length ; i++) {
  26.             stack.push(Integer.parseInt(arr[i]));
  27.         }
  28.         return construct(Integer.MIN_VALUE,Integer.MAX_VALUE,stack);
  29.     }
  31.     private void postOrder(TreeNode root,List<Integer> list){
  32.         if (root == null) {
  33.             return;
  34.         }
  35.         postOrder(root.left,list);
  36.         postOrder(root.rigth,list);
  37.         list.add(root.val);
  38.     }
  40.     private TreeNode contruct (int lower,int upper,Deque<Integer> stack) {
  41.         if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) {
  42.             return null;
  43.         }
  44.         int val = stack.pop();
  45.         TreeNode = new TreeNode(val);
  46.         root.right = construct(val,upper,stack);
  47.         root.left = construct(lower,val,stack);
  48.         return root;
  49.     }
  50. }

1022. 从根到叶的二进制数之和

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

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

这里面的 val = (val << 1) | root.val; 是取按位或的意思（有1就是1，全为0才是0）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public int sumRootToLeaf(TreeNode root) {
  18.         // 使用遍历，选择深度优先遍历
  19.         return dfs(root,0);
  20.     }
  22.     public int dfs(TreeNode root, int val){
  23.         if (root == null) {
  24.             return 0;
  25.         }
  26.         val = (val << 1) | root.val;
  27.         if(root.left == null && root.right == null) {
  28.             return val;
  29.         }
  30.         return dfs(root.left,val) + dfs(root.right,val);
  31.     }
  32. }