二叉树

一、二叉树的重要性

举个例子，比如说我们的经典算法「快速排序」和「归并排序」，对于这两个算法，你有什么理解？如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历，那么我就知道你是个算法高手了。

为什么快速排序和归并排序能和二叉树扯上关系？我们来简单分析一下他们的算法思想和代码框架：

快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

快速排序的代码框架如下：

void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/


    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？

再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。

归并排序的代码框架如下：

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);


    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}

先对左右子数组排序，然后合并（类似合并有序链表的逻辑），你看这是不是二叉树的后序遍历框架？另外，这不就是传说中的分治算法嘛，不过如此呀。

如果你一眼就识破这些排序算法的底细，还需要背这些算法代码吗？这不是手到擒来，从框架慢慢扩展就能写出算法了。

说了这么多，旨在说明，二叉树的算法思想的运用广泛，甚至可以说，只要涉及递归，都可以抽象成二叉树的问题。

二、二分查找树的实现

package tree;

public class BST {
    /**
     * 二分查找树满足以下的特性：
     * 每个节点都比自己左子树上的节点大，并比右子树上的节点小。
     * BST does not allow nodes with the same value
     * <p>
     * O(T):O(logN)
     */

    static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }

        public TreeNode() {

        }
    }

    /**
     * 定义treeNode
     **/
    private TreeNode root;


    /**
     * 跳出循环后，如果是因为current==null而跳出的，则返回null
     * 如果不是，则默认是current跳出的，所以返回的是current
     *
     * @param key 输入的想要查找的值
     * @return 返回null 或者是get到的值value
     */
    public TreeNode get(int key) {
        TreeNode current = root;
        while (current != null && current.value != key) {
            if (key < current.value) {
                current = current.left;
            } else if (key > current.value) {
                current = current.right;
            }
        }
        return current == null ? null : current;
    }


    /**
     * 插入需要两个值
     * 一个父亲节点，一个当前节点
     * <p>
     * void 函数仍然用return的意思是相当于终止函数
     *
     * @param key
     */
    public void insert(int key) {

        // 先判断是否存在，不存在则让输入为root
        if (root == null) {
            root = new TreeNode(key);
            return;
        }

        // current 代表你要插入的值
        // parent 插入的父亲

        TreeNode current = root;
        TreeNode parent = null;
        while (true) {
            parent = current;
            if (key < parent.value) {
                current = parent.left;
                if (current == null) {
                    parent.left = new TreeNode(key);
                    return;
                }
            } else if (key > parent.value) {
                current = parent.right;
                if (current == null) {
                    parent.right = new TreeNode(key);
                    return;
                }
            } else {
                return; // BST does not allow nodes with the same value
            }
        }
    }

    /**
     * 删除需要考虑三种情况
     * <p>
     * Case 1: if node to be deleted has no children （删除节点没有子节点）
     * Case 2: if node to be deleted has only one child （删除节点有一个子节点，可以是左，也可以是右）
     * Case 3: current.left != null && current.right != null （删除节点有两个节点，左右节点都存在）
     *
     * https://www.bilibili.com/video/BV1qQ4y1M7Z4
     *
     * @param key
     * @return
     * @insideparam parent: 用来记录上一个父亲节点
     * @insideparam current：用来记录当前的节点
     */
    public boolean delete(int key) {
        TreeNode parent = root;
        TreeNode current = root;
        boolean isLeftChild = false;
        while (current != null && current.value != key) {
            parent = current;
            if (current.value > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
        }
        if (current == null) {
            return false;
        }
        // Case 1: if node to be deleted has no children
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            // Case 2: if node to be deleted has only one child
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left; // 和下方不一致的主要是current.left 和current.right 的区别
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
            // Case 3: current.left != null && current.right != null
            // 找右子树上的最小的节点来替代--> successor
        } else {
            // 这一步是获得最小的节点
            TreeNode successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    private TreeNode getSuccessor(TreeNode node) {
        // 找右子树上的最小的节点来替代--> successor
        // 同时遵循保证树形结构的完整
        TreeNode successor = null; // 最后需要放上去的那个节点
        TreeNode successorParent = null;
        TreeNode current = node.right; // 找到待删除位置的sub右子树上找到最小的点
        // 这里的while循环已经保证了最小左子树，但是没法保证最小左子树是否含有右节点
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 说明待删除的点是有左子树的
        if (successor != node.right) {
            // 这一步的目的是为了将最小左子树的有节点给连接上
            // 如果没有也就返回null，不影响
            successorParent.left = successor.right;
            successor.right = node.right;
        }
        return successor;
    }

    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.value);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

}

三、遍历树的方法(Tree traversal)

• Pre-order Traversal
  • 先访问节点自己，然后访问左子树，最后再访问右子树
• In-order Traversal
  • 先访问左子树上的节点，再访问自己，最后再访问右子树上的节点
• Post-order Traversal
  • 先访问左右子树，最后再访问自己

注意：以下的实现都是通过recursion来实现的

前序遍历 Preorder Traversal

在前序遍历中，先访问节点自己，然后访问左子树，最后再访问右子树，对于每个节点迭代此操作：

public static void preOrderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    System.out.println(root.value);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

中序遍历 Inorder Traversal

在中序遍历中，先访问左子树上的节点，再访问自己，最后再访问右子树上的节点：

public static void inOrderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    inOrderTraversal(root.left);
    System.out.println(root.value);
    inOrderTraversal(root.right);
}

后序遍历 Postorder Traversal

在后序遍历中，先访问左右子树，最后再访问自己：

public static void postOrderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.println(root.value);
}

例子

删除36

四、写递归算法的秘诀（二叉树）

我们前文 二叉树的最近公共祖先 写过，写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节。

怎么理解呢，我们用一个具体的例子来说，比如说让你计算一棵二叉树共有几个节点：

// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
    // base case
    if (root == null) return 0;
    // 自己加上子树的节点数就是整棵树的节点数
    return 1 + count(root.left) + count(root.right);
}

这个问题非常简单，大家应该都会写这段代码，root 本身就是一个节点，加上左右子树的节点数就是以 root 为根的树的节点总数。

左右子树的节点数怎么算？其实就是计算根为 root.left 和 root.right 两棵树的节点数呗，按照定义，递归调用 count 函数即可算出来。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

算法实践

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

通过观察，我们发现只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。

前序遍历

// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
    // base case
    if (root == null) {
        return null;
    }

    /**** 前序遍历位置 ****/
    // root 节点需要交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 让左右子节点继续翻转它们的子节点
    invertTree(root.left);
    invertTree(root.right);

    return root;
}

引申

利用前序遍历
class Solution {
        // 先序遍历--从顶向下交换
        public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            // 保存右子树
            TreeNode rightTree = root.right;
            // 交换左右子树的位置
            root.right = invertTree(root.left);
            root.left = invertTree(rightTree);
            return root;
        }
    }

利用中序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            invertTree(root.left); // 递归找到左节点
            TreeNode rightNode= root.right; // 保存右节点
            root.right = root.left;
            root.left = rightNode;
            // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
            invertTree(root.left); 
    }
}

利用后序遍历
 class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 后序遍历-- 从下向上交换
            if (root == null) return null;
            TreeNode leftNode = invertTree(root.left);
            TreeNode rightNode = invertTree(root.right);
            root.right = leftNode;
            root.left = rightNode;
            return root;
        }
    }

利用层次遍历
   class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 层次遍历--直接左右交换即可
            if (root == null) return null;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                TreeNode node = queue.poll();
                TreeNode rightTree = node.right;
                node.right = node.left;
                node.left = rightTree;
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            return root;
        }
    }

116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

节点 5 和节点 6 不属于同一个父节点，那么按照这段代码的逻辑，它俩就没办法被穿起来，这是不符合题意的。

回想刚才说的，二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。

那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」

Answer

// 主函数
Node connect(Node root) {
    if (root == null) return null;
    connectTwoNode(root.left, root.right);
    return root;
}

// 辅助函数
void connectTwoNode(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    /**** 前序遍历位置 ****/
    // 将传入的两个节点连接
    node1.next = node2;

    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    connectTwoNode(node1.right, node2.left);
}

114. 将二叉树展开为链表

函数签名如下：

void flatten(TreeNode root);

我们尝试给出这个函数的定义：

给 flatten 函数输入一个节点 root**，那么以 **root 为根的二叉树就会被拉平为一条链表。

我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：

1、将 root 的左子树和右子树拉平。

2、将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。

上面三步看起来最难的应该是第一步对吧，如何把 root 的左右子树拉平？其实很简单，按照 flatten 函数的定义，对 root 的左右子树递归调用 flatten 函数即可：

// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;

  	// 先把左右子树捋直
    flatten(root.left);
    flatten(root.right);


    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;


    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;


    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

public void flatten(TreeNode root) {
    if(root==null) return ;
    // 先把左右子树捋直
    flatten(root.left);
    flatten(root.right);
//把捋直的右子树备份一下
    TreeNode tmp = root.right;

  	//把捋直的左子树放到右边
    root.right = root.left;
  
  	//记得把左子树置空
    root.left = null;
//找到现在右子树的最后一个node
    while(root.right!=null){
        root = root.right;
    }
  	//把捋直的原来的右子树接上去
    root.right = tmp;
}

你看，这就是递归的魅力，你说 flatten 函数是怎么把左右子树拉平的？说不清楚，但是只要知道 flatten 的定义如此，相信这个定义，让 root 做它该做的事情，然后 flatten 函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。

注意： 一定要将左子树制零，否则会出现下面的情况

输入

[1,2,5,3,4,null,6]

输出

[1,2,2,3,3,3,3,null,4,null,4,null,4,null,4,null,5,null,5,null,5,null,5,null,6,null,6,null,6,null,6]

差别

预期结果

[1,null,2,null,3,null,4,null,5,null,6]

至此，这道题也解决了，我们旧文 k个一组翻转链表 的递归思路和本题也有一些类似。

297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Serialiazable

package tree;

public class Serializable {
    String SEP = ",";
    String NULL = "#";

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    /**
     * StringBuilder 可以用于高效拼接字符串，所以也可以认为是一个列表，
     * 用 , 作为分隔符，
     * 用 # 表示空指针 null，
     * 调用完 traverse 函数后，
     * StringBuilder 中的字符串应该是 1,2,#,4,#,#,3,#,#,。
     *
     * @param root
     * @param sb
     */
    public void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }

        // preOrder traverse
        sb.append(root.val).append(SEP);
        serialize(root.left, sb);
        serialize(root.right, sb);
    }


}

Deserializable

package tree;


import java.util.LinkedList;

public class Deserializable {
    String SEP = ",";
    String NULL = "null";


    public TreeNode deserializable(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserializable(nodes);
    }

    public TreeNode deserializable(LinkedList<String> nodes) {
        if (nodes.isEmpty()) return null;
        String first = nodes.removeFirst();
        if (first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));

        root.left = deserializable(nodes);
        root.right = deserializable(nodes);

        return root;
    }

}

105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

652. Find Duplicate Subtrees

难度中等291

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

Answer

class Solution {
    HashMap<String, Integer> memo = new HashMap<>();
    LinkedList<TreeNode> res = new LinkedList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    public String traverse(TreeNode root){
        if(root == null) return "null";
        String left = traverse(root.left);
        String right = traverse(root.right);
        String subTree = left+","+right+","+root.val;
        
        int freq = memo.getOrDefault(subTree,0);
        if(freq==1){
            res.add(root);
        }

        memo.put(subTree,freq+1);
        
        return subTree;

    }
}

你需要知道以下两点：

1、以我为根的这棵二叉树（子树）长啥样？

2、以其他节点为根的子树都长啥样？

这就叫知己知彼嘛，我得知道自己长啥样，还得知道别人长啥样，然后才能知道有没有人跟我重复，对不对？

好，那我们一个一个来解决，先来思考，我如何才能知道以自己为根的二叉树长啥样？

其实看到这个问题，就可以判断本题要使用「后序遍历」框架来解决：

void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
    /* 解法代码的位置 */
}

为什么？很简单呀，我要知道以自己为根的子树长啥样，是不是得先知道我的左右子树长啥样，再加上自己，就构成了整棵子树的样子？

如果你还绕不过来，我再来举个非常简单的例子：计算一棵二叉树有多少个节点。这个代码应该会写吧：

int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 先算出左右子树有多少节点
    int left = count(root.left);
    int right = count(root.right);
    /* 后序遍历代码位置 */
    // 加上自己，就是整棵二叉树的节点数
    int res = left + right + 1;
    return res;
}

这不就是标准的后序遍历框架嘛，和我们本题在思路上没啥区别对吧。

现在，明确了要用后序遍历，那应该怎么描述一棵二叉树的模样呢？我们前文 序列化和反序列化二叉树 其实写过了，二叉树的前序/中序/后序遍历结果可以描述二叉树的结构。

所以，我们可以通过拼接字符串的方式把二叉树序列化，看下代码：

String traverse(TreeNode root) {
    // 对于空节点，可以用一个特殊字符表示
    if (root == null) {
        return "#";
    }
    // 将左右子树序列化成字符串
    String left = traverse(root.left);
    String right = traverse(root.right);
    /* 后序遍历代码位置 */
    // 左右子树加上自己，就是以自己为根的二叉树序列化结果
    String subTree = left + "," + right + "," + root.val;
    return subTree;
}

我们用非数字的特殊符#表示空指针，并且用字符,分隔每个二叉树节点值，这属于序列化二叉树的套路了，不多说。

注意我们subTree是按照左子树、右子树、根节点这样的顺序拼接字符串，也就是后序遍历顺序。你完全可以按照前序或者中序的顺序拼接字符串，因为这里只是为了描述一棵二叉树的样子，什么顺序不重要。

这样，我们第一个问题就解决了，对于每个节点，递归函数中的subTree变量就可以描述以该节点为根的二叉树。

现在我们解决第二个问题，我知道了自己长啥样，怎么知道别人长啥样？这样我才能知道有没有其他子树跟我重复对吧。

这很简单呀，我们借助一个外部数据结构，让每个节点把自己子树的序列化结果存进去，这样，对于每个节点，不就可以知道有没有其他节点的子树和自己重复了么？

HashMap，额外记录每棵子树的出现次数，避免res中必然出现的重复