二叉树-EmiyaCC 摘录室

操作二叉树
- 翻转二叉树
- 填充每个节点的下一个右侧节点指针

二叉树转链表

二叉树展开为链表

链表转二叉树

最大二叉树
从前序与中序遍历序列构造二叉树
从中序与后序遍历序列构造二叉树
寻找重复的子树

高频面试题

二叉树的最近公共祖先

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历

操作二叉树

关于二叉树的操作，无非是 BFS 和 DFS（应该），大体的框架也可以总结出来

// DFS
class Solution {
    public E function(E root) {
        if (root == null) return root;
        E left = function(root.left);
        E right = function(root.right);
        // 此处是一些操作，位置可以变，在后面就是后序遍历，其他位置同理
        return root;
    }
}

// BFS 不分层
class Solution {
    public E function(E root) {
        if (root == null) return root;
        Queue<E> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            E tmp = queue.poll();
            // 此处是一些操作
            if (tmp.left != null) queue.offer(tmp.left);
            if (tmp.right != null) queue.offer(tmp.right);
        }
        return root;
    }
}
// BFS 分层
class Solution {
    public E function(E root) {
        if (root == null) return root;
        Queue<E> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 对比不分层，此处多了一个计数
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                E tmp = queue.poll();
                // 此处是一些操作
            	if (tmp.left != null) queue.offer(tmp.left);
            	if (tmp.right != null) queue.offer(tmp.right);
            }
        }
        return root;
    } 
}

翻转二叉树

// https://leetcode-cn.com/problems/invert-binary-tree/
// 前序遍历 递归 DFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

// 迭代 BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            TreeNode right = tmp.right;
            tmp.left = right;
            tmp.right = left;
            if (left != null) queue.offer(left);
            if (right != null) queue.offer(right);
        }
        return root;
    }
}

填充每个节点的下一个右侧节点指针

对于一般的题来说（对于我），BFS 相对来说更好写出来，因为迭代更好理解一点，但是递归写出来就感觉，有大侠之姿（仅仅是帅，一直压栈也不支持）

// https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
// 前序遍历 DFS
class Solution {
    public 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);
    }
}

// BFS 没什么好说的，对着模板，抄抄就行
class Solution {
    public Node connect(Node root) {
        if (root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                Node tmp = queue.poll();
                // 核心业务段，嗯，一句话
                if (i < size - 1) tmp.next = queue.peek();
                if (tmp.left != null) queue.offer(tmp.left);
                if (tmp.right != null) queue.offer(tmp.right);
            }
        }
        return root;
    }
}

二叉树转链表

在二叉树中做 DFS，大概分两种，一种是设置个全局变量，一个是函数传参，模板其实跟上面也一样

// 设置全局变量，大力出奇迹，奥里给
class Solution {
    Queue<TreeNode> queue = new LinkedList<>();

    public void function(E root) {
        if (root == null) return ;
        dfs(root);
        // 此处是操作
    }
	// 把结点放入队列中
    void dfs(E root) {
        if (root == null) return;
        // 在前面就是前序遍历
        queue.offer(root);
        dfs(root.left);
        dfs(root.right);
    }
}

// 函数传参，优雅点
class Solution {
    public void function(E root) {
        if (root == null) return ;
        Queue<E> queue = new LinkedList<>();
        queue = dfs(root, queue);
        // 此处是操作
    }

    Queue<E> dfs(E root, Queue<E> queue) {
        if (root == null) return new LinkedList(queue);
        // 在前面就是前序遍历
        queue.offer(root);
        dfs(root.left, queue);
        dfs(root.right, queue);
        return new LinkedList(queue);
    }
}

二叉树展开为链表

用 BFS 来做这题，首先肯定还是需要 DFS 整个链表的，得到顺序的链表后再去一个一个设置 left 和 right 的值；用 DFS 来做，稍微不好想一点，最后要把做拼接操作

// https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
// 使用 BFS ，大力出奇迹，但是空间复杂度不是 O（1），但是好想出来啊，附庸风雅的用传参的形式
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return ;
        Queue<TreeNode> queue = new LinkedList<>();
        queue = dfs(root, queue);
        int size = queue.size();
        for (int i = 0; i < size - 1; i ++) {
            TreeNode tmp = queue.poll();
            tmp.left = null;
            tmp.right = queue.peek();
        }
    }

    Queue<TreeNode> dfs(TreeNode root, Queue<TreeNode> queue) {
        if (root == null) return new LinkedList(queue);
        queue.offer(root);
        dfs(root.left, queue);
        dfs(root.right, queue);
        return new LinkedList(queue);
    }
} 

// 递归，后序遍历
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left);
        flatten(root.right);
        // 递归中，左右子树已经拉平
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 把左子树归位
        root.left = null;
        root.right = left;
        // 把右子树归位
        TreeNode tmp = root;
        while (tmp.right != null) {
            tmp = tmp.right;
        }
        // 把左子树和右子树拼接起来
        tmp.right = right;
    }
}

链表转二叉树

构造一个二叉树，主要是找到根节点位置，借此将原链表分成两半，再分而治之

最大二叉树

构造最大二叉树，首先找到根节点，也就是最大值的索引，然后分成两半，各自递归，再合并，完事。要注意的是需要构建一个 helper 函数，来帮助定义上下界

// https://leetcode-cn.com/problems/maximum-binary-tree/
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums, int left, int right) {
        if (left > right) return null;
        // 找到数组最大值和最大值索引
        int index = -1, maxVal = Integer.MIN_VALUE;
        for (int i = left; i <= right; i ++) {
            if (maxVal < nums[i]) {
                index = i;
                maxVal = nums[i];
            }
        }
        
        TreeNode root = new TreeNode(maxVal);
        root.left = build(nums, left, index - 1);
        root.right = build(nums, index + 1, right);
        return root;
    }
}

从前序与中序遍历序列构造二叉树

先将中序遍历的链表存入 indexMap 中，与上题的区别是上题找位置是一个一个比较找到值，而本题是用前序遍历第一个值就是根节点的特性，大体框架是一样的

// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) return null;

        int preorder_root = preorder_left;
        int inorder_root = indexMap.get(preorder[preorder_root]);
        int size_left_subtree = inorder_root - inorder_left;

        TreeNode root = new TreeNode(preorder[preorder_root]);
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
}
// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/

从中序与后序遍历序列构造二叉树

思路同上题

// https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length;
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(postorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] postorder, int[] inorder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {
        if (postorder_left > postorder_right) return null;

        int postorder_root = postorder_right;
        int inorder_root = indexMap.get(postorder[postorder_root]);
        int size_left_subtree = inorder_root - inorder_left;

        TreeNode root = new TreeNode(postorder[postorder_root]);
        // 与上题区别在于边界
        root.left = myBuildTree(postorder, inorder, postorder_left, postorder_left + size_left_subtree - 1, inorder_left, inorder_root - 1);
        root.right = myBuildTree(postorder, inorder, postorder_left + size_left_subtree, postorder_right - 1, inorder_root + 1, inorder_right);
        return root;
    }
}

寻找重复的子树

大体思路是每个节点的形状转换成 String 存储在 map 中，然后递归对比每个节点，如果 map 已经有了就说明两个节点是重复子树的头节点

// https://leetcode-cn.com/problems/find-duplicate-subtrees/
class Solution {
    HashMap<String, Integer> map = new HashMap<>();
    LinkedList<TreeNode> list = new LinkedList<>();

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

    String traverse(TreeNode root) {
        if (root == null) return "#";
        String left = traverse(root.left);
        String right = traverse(root.right);
        String compare = left + "," + right + "," + root.val;
        map.put(compare, map.getOrDefault(compare, 0) + 1);
        if (map.get(compare) == 2) {
            list.add(root);
        }
        return compare;
    }
}
// https://leetcode-cn.com/problems/find-duplicate-subtrees/solution/xun-zhao-zhong-fu-de-zi-shu-by-leetcode/

高频面试题

二叉树的最近公共祖先

// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
// 核心是找该结点下的子树有没有 p q 结点
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        else if (left != null) return left;
        else return right;
    }
}
// K神的剑指offer

Reference：

https://labuladong.gitee.io/algo

https://leetcode-cn.com/problems/