Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • Construct Binary Tree from Preorder and Inorder Traversal
  • 对于任意指定子树,在 inorder / preorder / postorder 中都是长度一样的连续 subarray,只是位置不同。
  • 同一题一个比较 pythonic 的解法甚至不需要像 java 一样定义区间
  • Construct Binary Tree from Inorder and Postorder Traversal
  • Serialize and Deserialize Binary Tree
  • 解决这题的关键就是,自己补位,构建一个 full binary tree 出来。
  • 另外一个经验是,处理字符串的时候尽量直接用内置函数,比如 str.indexOf('x') 这种,知道题的重点不是字符串就别每次都手写了。
  • 论坛上比较简洁正规的 pre-order DFS 递归写法:
  • 这个写法里会在 queue 里放入 null.
  • 核心思想是,用 # 补位,构造一个 "full binary tree",每个节点有 0 / 2 个子节点。因此在我们构造树的过程中,我们永远可以一次看两个元素,并且把子节点加入队列,保证算法的正确性。
  • 在 Binary Tree 的各种遍历中,BFS 都是比较耗费空间的一种,所以一个显然的优化与 follow up 就是,能不能用 DFS ,迭代做。
  • 去论坛看了一圈,发现对于 full binary tree,pre-order 和 in-order 的 DFS 都行,挺有意思的~
  • 这种做法其实就是一种对 pre-order DFS 做法的 Stack 模拟。也是 Tree 类问题递归转迭代的常用手段。
  • Verify Preorder Serialization of a Binary Tree
  • 另一种妖孽的写法是 dietpepsi 的 graph degree 思路,在这个帖子
  • 这个思路可以验 pre-order 与 post-order 的 serialization.
  • 最后一个思路是,借鉴这章之前 Serialization 的 pre-order 重建法,保存 doLeft 的 boolean 变量模拟重建树的过程。当然,这里 stack 存的其实是一个 stack frame,而不再是具体 node,左右子树也不重要了。

Was this helpful?

  1. Binary Tree,二叉树

创建 / 序列化

Previous修改结构Next子树组合,BST query

Last updated 4 years ago

Was this helpful?

  • 要学会用 continuous subarray 的眼光去看三序遍历数组,子树结构 = 子序列结构

  • 对于任意指定子树,在 inorder / preorder / postorder 中都是长度一样的连续 subarray,只是位置不同。

这题挺常见的,而且在树类问题里我也很喜欢,很考察对于树的理解。

             [1] 
           /     \ 
         [5]      [4]
        /   \       \ 
      [2]   [3]      [6] 
                    /
                  [7]
  • In-order: 【(2,5,3) 1 (4,7,6)】

  • Pre-order: 【1 (5,2,3) (4,6,7)】

  • Post-order: 【(2,3,5) (7,6,4) 1】

In-order 和 pre-order 单独都只能提供一部分树的信息,只依靠一个无法建立出完全一样的树,因为有歧义。

  • In-order : 对于指定位置 index 的 root

    • 对于每个 tree / subtree, array 结构

    • 【左子树】【root】【右子树】

  • Pre-order:

    • 对于每个 tree / subtree, array 结构

    • 【root】【左子树】【右子树】

  • Post-order:

    • 对于每个 tree / subtree, array 结构

    • 【左子树】【右子树】【root】

递归建树的过程是

  • 建当前 root;

  • 建 左/右 子树;

  • 建 右/左 子树;

因此根据 inorder 和 preorder 的性质,我们用 preorder 的顺序决定“先建哪个为 root”,用 inorder 的相对位置决定 “左右子树是谁”。

因此这个问题是关于 preorder 的遍历,对于每个元素要在 inorder 中寻找相对位置。

对于任意指定子树,在 inorder / preorder / postorder 中都是长度一样的连续 subarray,只是位置不同。

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int preorderIndex, 
                           int inorderStart, int inorderEnd){
        if(inorderStart > inorderEnd || preorderIndex >= preorder.length) return null;

        int rootVal = preorder[preorderIndex];
        int pos = inorderStart;
        for(int i = inorderStart; i <= inorderEnd; i++){
            if(inorder[i] == rootVal){
                pos = i;
                break;
            }
        }

        int leftSubTreeLength = pos - inorderStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, inorder, preorderIndex + 1, inorderStart, pos - 1);
        root.right = build(preorder, inorder, preorderIndex + leftSubTreeLength + 1, pos + 1, inorderEnd);

        return root;
    }
}

同一题一个比较 pythonic 的解法甚至不需要像 java 一样定义区间

class Solution: 
    def buildTree(
        self, 
        preorder: List[int], 
        inorder: List[int]
    ) -> TreeNode: 
        return self.buildHelper(preorder, inorder)

    def buildHelper(
        self, 
        preorder: List[int], 
        inorder: List[int], 
    ) -> TreeNode:
        if len(preorder) == 0:
            return None
        if len(inorder) == 0:
            return None
        # create node 
    
        node = TreeNode(preorder.pop(0))
    
        in_order_index = inorder.index(node.val)
        in_order_len = len(inorder)
    
        # build left tree
        node.left = self.buildHelper(
            preorder, 
            inorder[0:in_order_index], 
        )
        # build right tree
        node.right = self.buildHelper(
            preorder, 
            inorder[in_order_index+1:], 
        )
    
        return node

掌握了这个性质之后,把 preorder 换成 postorder 也是一样的配方,一样的味道。

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int index, int inorderStart, int inorderEnd){
        if(inorderStart > inorderEnd || index < 0) return null;

        int rootVal = postorder[index];
        int pos = inorderStart;
        for(int i = inorderStart; i <= inorderEnd; i++){
            if(inorder[i] == rootVal){
                pos = i;
                break;
            }
        }

        int rightSubtreeLength = inorderEnd - pos;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(inorder, postorder, index - rightSubtreeLength - 1, inorderStart, pos - 1);
        root.right = build(inorder, postorder, index - 1, pos + 1, inorderEnd);

        return root;
    }
}

这也是个很有意思的问题,核心问题类似于 encode / decode strings,在于 “如何确定唯一的 binary tree ?” 对于 List of String 来讲,只需要正确做好单词的分隔还有分隔符的消除歧义;而 Tree 上可以有 level 的分隔,left / right subtree 的分隔。

相对来讲Tree的优势是,这个 TreeNode 里面只存数字,所以有很多额外的字母和符号可以利用,不用担心所用字符的歧义问题(不然就得定义 escape 符了)

  • If given Tree is Binary Search Tree?

    If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.

  • If given Binary Tree is Complete Tree?

    A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.

  • If given Binary Tree is Full Tree?

    A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.

  • How to store a general Binary Tree?

    A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree. We can save space by storing Preorder traversal and a marker for NULL pointers.

解决这题的关键就是,自己补位,构建一个 full binary tree 出来。

自己第一遍 AC 的代码。思想就是做 preorder ,不过把左右子树分别用括号括起来。空节点会生成空括号。这样对于一棵子树的 substring,第一个 matching 括号就代表左子树,后面的就是右子树。

这种写法的好处一是和这章之前的思想有联系和继承,第二是不需要用逗号做分隔(但是每个叶节点会生成一对空括号)

递归的时候注意抹去括号的 index 细节,并且在一开始检查下是不是 "()".

另外一个经验是,处理字符串的时候尽量直接用内置函数,比如 str.indexOf('x') 这种,知道题的重点不是字符串就别每次都手写了。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";

        String left = serialize(root.left);
        String right = serialize(root.right);

        return Integer.toString(root.val) + "(" + left + ")" + "(" + right + ")";
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;
        if(data.equals("()")) return null;

        int indexFirstLeft = data.indexOf('(');
        int rootVal = Integer.parseInt(data.substring(0, indexFirstLeft));

        int leftCount = 1;
        int indexMatchingRight = indexFirstLeft + 1;

        while(indexMatchingRight < data.length() && leftCount != 0){
            if(data.charAt(indexMatchingRight) == '(') leftCount ++;
            if(data.charAt(indexMatchingRight) == ')') leftCount --;

            indexMatchingRight ++;
        }

        String leftSubtree = data.substring(indexFirstLeft + 1, indexMatchingRight - 1);
        String rightSubtree = data.substring(indexMatchingRight + 1, data.length() - 1);

        TreeNode root = new TreeNode(rootVal);
        root.left = deserialize(leftSubtree);
        root.right = deserialize(rightSubtree);

        return root;
    }
}

论坛上比较简洁正规的 pre-order DFS 递归写法:

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

    private void dfsSerialize(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append("#").append(" ");
            return;
        }

        sb.append(root.val).append(" ");
        dfsSerialize(root.left, sb);
        dfsSerialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(" ");
        int[] index = new int[1];

        return dfsDeserialize(strs, index);
    }

    private TreeNode dfsDeserialize(String[] strs, int[] index){
        if(strs[index[0]].equals("#")){
            index[0]++;
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(strs[index[0]]));
        index[0]++;
        root.left = dfsDeserialize(strs, index);
        root.right = dfsDeserialize(strs, index);

        return root;
    }

另一种写法是 BFS,源代码是 LeetCode 论坛上的:

这个写法里会在 queue 里放入 null.

核心思想是,用 # 补位,构造一个 "full binary tree",每个节点有 0 / 2 个子节点。因此在我们构造树的过程中,我们永远可以一次看两个元素,并且把子节点加入队列,保证算法的正确性。

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        StringBuilder res = new StringBuilder();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                res.append("#,");
                continue;
            }
            res.append(node.val + ",");
            q.add(node.left);
            q.add(node.right);
        }
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == "") return null;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        String[] values = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        q.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("#")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                q.add(left);
            }
            if (!values[++i].equals("#")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                q.add(right);
            }
        }
        return root;
    }
}

在 Binary Tree 的各种遍历中,BFS 都是比较耗费空间的一种,所以一个显然的优化与 follow up 就是,能不能用 DFS ,迭代做。

去论坛看了一圈,发现对于 full binary tree,pre-order 和 in-order 的 DFS 都行,挺有意思的~

这种做法其实就是一种对 pre-order DFS 做法的 Stack 模拟。也是 Tree 类问题递归转迭代的常用手段。

  • 关键点1: 要存一个 boolean 记录下当前要填的点是不是左节点;

  • 关键点2:这个 boolean 的变化要看当前 boolean 值以及新填上的点是不是叶节点;

  • 关键点3:对于填充右节点的情况,链接完了就直接 pop(),有别于填充左子树时候用的 peek(). 因为 preorder 右子树结束之后 stack frame 就出栈了。

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node == null){
                sb.append("#").append(" ");
                continue;
            }

            sb.append(node.val).append(" ");
            stack.push(node.right);
            stack.push(node.left);
        }
        return sb.toString().trim();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Stack<TreeNode> stack = new Stack<>();
        String[] strs = data.split(" ");
        if(strs[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        stack.push(root);
        int index = 1;
        boolean doLeft = true;
        while(index < strs.length){
            String str = strs[index++];
            TreeNode node = (str.equals("#")) 
                            ? null
                            : new TreeNode(Integer.parseInt(str));
            if(doLeft){
                stack.peek().left = node;
                if(node == null) doLeft = false;
            } else {
                stack.pop().right = node;
                if(node != null) doLeft = true;
            }

            if(node != null) stack.push(node);
        }
        return root;
    }

先贴个用自己理解写的做法:

Stack 里面存 node ,记录来路,对于每个 node,存一个 boolean 表示 “左子树处理完没”。这样当我们每次处理完一个 node 之后,都以栈顶为准,如果栈顶 boolean = false,就设成 true,代表左子树看完了,开始看右子树;否则就一路 pop 到第一个左子树没处理完的节点为止。

  • corner case1: "#" 代表空树,合法;

  • corner case2: stack 只能空一次,中间如果再出现 stack 为空然后往里加 node 的情况,说明是多个 root,返回 false;

public class Solution {
    private class Node{
        boolean isLDone;
        public Node(){
            isLDone = false;
        }
    }

    public boolean isValidSerialization(String preorder) {
        if(preorder.equals("#")) return true;

        Stack<Node> stack = new Stack<>(); 
        String[] strs = preorder.split(",");

        for(int i = 0; i < strs.length; i++){
            // Multiple roots
            if(i != 0 && stack.isEmpty()) return false;

            String str = strs[i];
            if(str.equals("#")){
                // Invalid leaf
                if(stack.isEmpty()) return false;
                Node top = stack.peek();
                if(!top.isLDone){
                    top.isLDone = true;
                } else {
                    while(!stack.isEmpty()){
                        stack.pop();
                        if(!stack.isEmpty() && !stack.peek().isLDone){
                            stack.peek().isLDone = true;
                            break;
                        }
                    }
                }
            } else {
                stack.push(new Node());
            }
        }

        return stack.isEmpty();
    }
}

这个思路可以验 pre-order 与 post-order 的 serialization.

  • all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root

  • all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

最后一个思路是,借鉴这章之前 Serialization 的 pre-order 重建法,保存 doLeft 的 boolean 变量模拟重建树的过程。当然,这里 stack 存的其实是一个 stack frame,而不再是具体 node,左右子树也不重要了。

    private class TreeNode{
        int val;
        public TreeNode(int val){
            this.val = val;
        }
    }

    public boolean isValidSerialization(String preorder) {
        if(preorder.equals("#")) return true;

        Stack<TreeNode> stack = new Stack<>(); 
        String[] strs = preorder.split(",");
        TreeNode root = (!strs[0].equals("#"))
                        ? new TreeNode(0)
                        : null;
        stack.push(root);
        boolean doLeft = true;

        for(int i = 1; i < strs.length; i++){
            // Multiple roots
            if(i != 0 && stack.isEmpty()) return false;
            if(stack.peek() == null) return false;

            String str = strs[i];
            TreeNode node = (str.equals("#"))
                            ? null 
                            : new TreeNode(0);

            if(doLeft){
                if(node == null) doLeft = false;
            } else {
                if(stack.isEmpty()) return false;
                stack.pop();
                if(node != null) doLeft = true;
            }
            if(node != null) stack.push(node);
        }

        return stack.isEmpty();
    }

另一种妖孽的写法是 dietpepsi 的 graph degree 思路,在

Construct Binary Tree from Preorder and Inorder Traversal
Construct Binary Tree from Inorder and Postorder Traversal
Serialize and Deserialize Binary Tree
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
Verify Preorder Serialization of a Binary Tree
这个帖子