数据结构——树

作者: yaco | 来源:发表于2020-03-27 22:38 被阅读0次

有关树的算法题总结

实现二叉树的前序、中序、后序遍历（递归、非递归，mirros方法）
查找后继节点
二叉树的序列化和反序列化
各种二叉树的识别问题
求完全二叉树的节点个数
树形DP问题

树结构基础

传送门——二叉搜索树(Binary Search Tree)的实现
 传送门——平衡二叉搜索树(Balance Binary Tree)的实现
 传送门——线索化二叉树

入门——实现二叉树的前序、中序、后序遍历（递归、非递归，mirros方法）

递归方式下的前中后遍历

    // 前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            ans.add(root.val);
            if(root.left != null){
                ans.addAll(inorderTraversal(root.left));
            }
            if(root.right != null){
                ans.addAll(inorderTraversal(root.right));
            }
        }
        return ans;
    }

    // 中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            if(root.left != null){
                ans.addAll(inorderTraversal(root.left));
            }
            ans.add(root.val);
            if(root.right != null){
                ans.addAll(inorderTraversal(root.right));
            }
        }
        return ans;
    }
    
    // 后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null) {
            if(root.left != null){
                ans.addAll(postorderTraversal(root.left));
            }
            if(root.right != null){
                ans.addAll(postorderTraversal(root.right));
            }
            ans.add(root.val);
        }
        return ans;
    }
}

非递归的方式实现三种遍历

前序：用栈来代替系统栈，首先将root压入栈，每次取出栈顶元素的时候，将值加入ans，弹出的同时，压入root的左右子树，因为要保证先左子树，再右子树，所以因该先压右子树，再压左子树。
中序：同样使用栈，只要栈空或者当前节点的左子树不为空，就不停的压栈，当某个节点没有左子树时，那么出栈，出栈同时加进ans，然后将其右子树入栈，重复相同的操作
后序：前序遍历的顺序为：中 - 左 - 右，后序遍历要实现的顺序为左 - 右 - 中，那么可以按照前序遍历的思路，用一个栈先压成中 - 右 - 左的顺序，那么依次出栈，就时后序遍历的顺序
具体看代码：

    // 前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                root = stack.pop();
                ans.add(root.val);
                if(root.right != null){
                    stack.push(root.right);
                }
                if(root.left != null){
                    stack.push(root.left);
                }
            }
        }
        return ans;
    }

    // 中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            Stack<TreeNode> stack = new Stack<>();
            while(!stack.isEmpty() || root != null){
                if(root != null){
                    stack.push(root);
                    root = root.left;
                }else{
                    root = stack.pop();
                    ans.add(root.val);
                    root = root.right;
                }
            }
        }
        return ans;
    }

    // 后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<Integer> data = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                root = stack.pop();
                data.push(root.val);
                if(root.left != null){
                    stack.push(root.left);
                }
                if(root.right != null){
                    stack.push(root.right);
                }
            }
            // 将data数据返回
            while(!data.isEmpty()){
                ans.add(data.pop());
            }
        }
        return ans;
    }

鬼斧神工——Morris遍历
Morris遍历使用二叉树节点中大量指向null的指针，由Joseph Morris 于1979年发明。
时间复杂度：O(n)
额外空间复杂度：O(1)

一张图理解Morris遍历路线

Morris遍历

通用的Morris遍历路线入上图所示：
首先不停的向左子树搜索，连接出所有的路径，等到了最左边的子节点，开始不停的向右走，一边走一边关闭之前开辟的路径。

    // 基础莫里斯遍历（没有添加遍历元素的添加）
    public List<Integer> Morris(TreeNode root){
        List<Integer> ans = new ArrayList<>();
        if(root != null) {
            TreeNode cur1 = root;   // 记录当前遍历的节点
            TreeNode cur2 = null;   // 记录当前节点的左子节点
            while(cur1 != null){
                cur2 = cur1.left;
                if(cur2 != null){
                    // 一直向右搜索，直到空或者回到了原始位置结束
                    while(cur2.right != null && cur2.right != cur1){
                        cur2 = cur2.right;
                    }
                    // 如果沿着cur2一直找到了空，表示为第一次遍历，那么连接到开始遍历的地方，且cur2继续向左走，去连接下面的节点
                    if(cur2.right == null){
                        cur2.right = cur1;   // cur1和cur2连接
                        cur1 = cur1.left;
                        continue;
                    }else{
                        cur2.right = null;
                    }
                }
                cur1 = cur1.right;
            }
        }
        return ans;
    }

在基础的Morris代码块之上，按照遍历要求填入不同的操作, 前序，中序，后序分别如下：

前序遍历：
前序遍历的顺序是完全按照Mrris找连接点的顺序来的，所以在断开连接的时候已经进行了二次访问，一定不可加操作，若以在cur2找到连接点或者cur2为null的时候加操作。

    // Morris前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            TreeNode cur1 = root;
            TreeNode cur2 = null;
            while(cur1 != null){
                cur2 = cur1.left;
                if(cur2 != null){
                    while(cur2.right != null && cur2.right != cur1){
                        cur2 = cur2.right;
                    }
                    if(cur2.right == null){
                        cur2.right = cur1;
                        ans.add(cur1.val);
                        cur1 = cur1.left;
                        continue;
                    }else{
                        cur2.right = null;
                    }
                }else{
                    ans.add(cur1.val);
                }
                cur1 = cur1.right;   // 入座left为null，或者cur2断开连接了，一直向右走
            }
        }
        return ans;
    }

中序遍历：

观察遍历顺序可知，中序遍历的顺序和cur1向右走的顺序完全一致，所以只需要在cur1右移之前添加到结果集就行

    // Morris中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            TreeNode cur1 = root;
            TreeNode cur2 = null;
            while(cur1 != null){
                cur2 = cur1.left;
                if(cur2 != null){
                    while(cur2.right != null && cur2.right != cur1){
                        cur2 = cur2.right;
                    }
                    if(cur2.right == null){
                        cur2.right = cur1;
                        cur1 = cur1.left;
                        continue;
                    }else{
                        cur2.right = null;
                    }
                }
                ans.add(cur1.val);
                cur1 = cur1.right;   // 入座left为null，或者cur2断开连接了，一直向右走
            }
        }
        return ans;
    }

后序遍历：

最难的就是后序遍历了，给一张图理解后序遍历的路线。

后序遍历
如果，他是按照右子树构成的链表逆序打印，那么只要当cur2进行断连接的时候，逆序打印cur1的left
例如：
当cur1在2的位置，cur2此时即将断开4-2之间的连接，那么逆序打印4
当cur1在1的位置，cur2此时即将断开5-1之间的连接，那么逆序打印2 - 5
当cur1在3的位置，cur2此时即将断开6-3之间的连接，那么逆序打印6
最后循环结束的时候，逆序打印 1 - 3 - 7, 完成逆序打印。

    // Morris后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if(root != null){
            TreeNode cur1 = root;
            TreeNode cur2 = null;
            while(cur1 != null){
                cur2 = cur1.left;
                if(cur2 != null){
                    while(cur2.right != null && cur2.right != cur1){
                        cur2 = cur2.right;
                    }
                    if(cur2.right == null){
                        cur2.right = cur1;
                        cur1 = cur1.left;
                        continue;
                    }else{
                        cur2.right = null;
                        helper(ans,cur1.left);
                    }
                }
                cur1 = cur1.right;   // 入座left为null，或者cur2断开连接了，一直向右走
            }
            helper(ans,root);
        }
        return ans;
    }
    
    // 逆序添加节点到ans
    private void helper(List<Integer> ans, TreeNode root){
        TreeNode cur = reverseTree(root);
        TreeNode temp = cur;
        while(temp != null){
            ans.add(temp.val);
            temp = temp.right;
        }
        reverseTree(cur);
    }
    
    // 写一个反转链表的方法
    private TreeNode  reverseTree(TreeNode root){
        TreeNode pre = null;
        TreeNode next = null;
        while(root != null){
            next = root.right;
            root.right = pre;
            pre = root;
            root = next;
        }
        return pre;
    }

查找后继节点

一、在普通二叉树中找到一个节点的后继节点
【题目】现在有一种新的二叉树节点类型如下：
public class Node { 
     public int value;
     public Node left;
     public Node right; 
     public Node parent;
     public Node(int data) { this.value = data; 
}
该结构比普通二叉树节点结构多了一个指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。只给一个在
二叉树中的某个节点 node，请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。

分析：分情况讨论：

如果节点的右孩子不为空时，返回右子树中最小的孩子
如果节点的右孩子为空，那么一直向上去找，直到当前节点是父节点的左孩子，或者当前节点的父节点为null

    /**
     * 返回一个节点的后继节点
     * @param node
     * @return
     */
    public static Node getSuccessorNode(Node node) {
        if(node == null) return null;
        // 如果节点的右孩子不为空时，返回右子树中最小的孩子
        if(node.right != null) {
            return getLeftMost(node.right);
        }else{
            //如果节点的右孩子为空，那么一直向上去找，直到当前节点是父节点的左孩子，或者当前节点的父节点为null
            Node parent = node.parent;
            while(parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    /**
     * 给定一个节点，返回树中最左边的值
     * @param node
     * @return
     */
    private static Node getLeftMost(Node node) {
        if(node == null) return node;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

二、在二叉搜索树中寻找下一个节点
LintCode448. 搜索树的中序后继节点
LeeCode04.06 后继者
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

思考：递归
首先本题中的二叉树还是个二叉搜索树，也就是中序遍历是单调递增的，所以我们可以利用这个性质来简化查找过程。
如果结点 p 的值大于等于 root 的值，说明 p 的后继结点在 root 右子树中，那么就递归到右子树中查找。
如果结点 p 的值小于 root 的值，说明 p 在 root 左子树中，而它的后继结点有两种可能，要么也在左子树中，要么就是 root：
--如果左子树中找到了后继结点，那就直接返回答案。
--如果左子树中没有找到后继结点，那就说明 p 的右儿子为空，那么 root 就是它的后继结点。

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // write your code here
        // 边界条件： 如果当前root为空，返回null
        if(root == null) return null;
        if(p.val >= root.val){
            // 如果p的值大于等于root的值，那么输出右子树搜索的结果
            return inorderSuccessor(root.right,p);
        }else{
            // 如果p的值小于root的值，那么如果左子树找到了p的后继节点，则返回，没找到则返回当前的root
            TreeNode left = inorderSuccessor(root.left,p);
            return left == null ? root : left;
        }
    }

二叉树的序列化和反序列化

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

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

按照前序遍历的顺序进行序列化二叉树 ————递归实现

首先当前的字符串序列化加到结果集（当前节点值加分隔符"_"), 然后将左边的序列化结果，加入结果集，然后将右边的序列化结果加入结果集，构建递归过程
反序列化同理，首先将字符串以分割符"_" 分割成为字符串数组，然后将字符串按顺序加入对立，通过队列以前序遍历递归的方式进行二叉树的恢复
代码如下：

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "#_";
        String ans = root.val + "_";
        ans += serialize(root.left);
        ans += serialize(root.right);
        return ans;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split("_");
        Queue<String> queue = new LinkedList<>();
        for(String s : strs){
            queue.add(s);
        }
        return getAnsTree(queue);
    }
    
    private TreeNode getAnsTree(Queue<String> queue){
        String s = queue.poll();
        if(s.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s));
        root.left = getAnsTree(queue);
        root.right = getAnsTree(queue);
        return root;
    }
}

按照层次遍历的顺序进行序列化二叉树————非递归实现

序列化：借助队列，每次序列化当前节点左右两个子节点，如果有孩子，则将孩子加入队列，然后再依次取出孩子进行孩子的孩子序列化
反序列化：同样借助队列，每次生成的一个有效节点时，都将其加入队列，当面后面取出，给其加上左右子孩子

    /**
     * 按层遍历序列化字符串
     * @param head
     * @return
     */
    public static String serialByLevel(Node head) {
        if(head == null) return "#!";
        String res = head.value + "!";
        // 借助队列，一层依次的遍历添加元素
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while(!queue.isEmpty()){
            head = queue.poll();
            if(head.left != null){
                res += head.left.value + "!";
                queue.add(head.left);
            }else{
                res += "#!";
            }
            if(head.right != null){
                res += head.right.value + "!";
                queue.add(head.right);
            }else{
                res += "#!";
            }
        }
        return res;
    }

    /**
     * 按层序列化的字符串进行还原(非递归实现)
     * @param levelStr
     * @return
     */
    public static Node reconByLevelString(String levelStr) {
        String[] values = levelStr.split("!");
        int index = 0;
        // 同样借助队列，没生成一个有效节点，就将其入队列，然后在该队列下面添加元素
        Queue<Node> queue = new LinkedList<Node>();
        Node head = generateNodeByString(values[index++]);
        if(head != null) {
            queue.offer(head);
        }
        Node node = null;
        while(!queue.isEmpty()){
            node = queue.poll();
            node.left = generateNodeByString(values[index++]);
            node.right = generateNodeByString(values[index++]);
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
        }
        return head;
    }

    /**
     * 按照字符串创建节点
     * @param value
     * @return
     */
    private static Node generateNodeByString(String value) {
        if(value.equals("#")) return null;
        return new Node(Integer.valueOf(value));
    }

各种二叉树的识别汇总

判断一颗树是否是搜索二叉树（BST —— Binary Search Tree）
判断一棵树是否是完全二叉树（CBT —— Complete Binary Tree）
判断一棵树是否是平衡二叉树（AVL —— Balance Binary Tree）

判断一颗树是否是搜索二叉树（BST —— Binary Search Tree）

思路一：按照非递归版的中序遍历的顺序，依次遍历如果当前元素小于前面的元素，则不是平衡二叉树。
思路二：暴力递归，没遍历到一个节点的时候，给节点加上上下限，如果大于上限或者小于下限都直接false
思路三：树形DP（树形动态规划，暴力递归的一种进阶）————求树的递归问题，首先明确我们需要的参数，然后将所需参数构成结果集粉装成为递归函数的返回体，然后由主函数整理使用。

    /**
     * 解法一： 中序遍历的方法进行比较
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        long cur = Long.MIN_VALUE;   // 注意这里必须用long，否则首位如果是Integer.MIN_VALUE,就回报错
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (root.val <= cur) {
                    return false;
                }
                cur = root.val;
                root = root.right;
            }
        }
        return true;
    }




    /**
     * 方法二：递归的思想
     * @param root
     * @return
     */
    public boolean isValidBST2(TreeNode root) {
        // 头节点没头范围的限制，litter和upper位置直接上null
        return process(root,null,null);
    }

    /**
     * 递归体
     * @param root   根节点
     * @param litter 当前的节点值得下限
     * @param upper  当前得节点值得上限
     * @return
     */
    private boolean process(TreeNode root, Integer litter, Integer upper) {
        if (root == null) return true;  // root为null,直接true

        int val = root.val;
        if (litter != null && val <= litter) return false;  // 如果有下限，向右走了，有了之前的根节点作为下限，超限则直接false
        if (upper != null && val >= upper) return false;    // 如果有下限，向左走了，有了之前的根节点作为下限，超限则直接false

        if (!process(root.right, val, upper)) return false; // 向右走，提供下限
        if (!process(root.left, litter, val)) return false; // 向左走，提供上限

        return true;
    }



    // 解法三：树形Dp
    public boolean isValidBST3(TreeNode root){
        if(root == null){
            return true;
        }
        return process3(root).isBST;
    }

    // 封装结果集
    public class ResultData{
        boolean isBST;
        long max;
        long min;

        public ResultData(boolean isBST, long max, long min){
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    // 递归体
    private ResultData process3(TreeNode root) {
        // 如果为null，min返回最大，max返回最小
        if(root == null) return new ResultData(true,Long.MIN_VALUE, Long.MAX_VALUE);
        // 首先求出左右子树的结果集
        ResultData left = process3(root.left);
        ResultData right = process3(root.right);
        // 对比分析： 左右都必须为BST，且root.val 大于左子树最大值，小于右子树最小值，返回结果，找出最小值和最大值返回
        if(left.isBST && right.isBST && (left.max < root.val) && (root.val < right.min)){
            return new ResultData(true,Math.max(Math.max(left.max,right.max),root.val),Math.min(Math.min(left.min,right.min),root.val));
        }
        return new ResultData(false,0,0);
    }

判断一棵树是否是完全二叉树（CBT —— Complete Binary Tree））

完全二叉树的性质：每个子树都是一个完全二叉树，最后一层如果有元素，一定从左边开始向有依次存在。
思路：
按照层次遍历的顺序遍历二叉树，如果当前遍历到的孩子孩子存在一个或者两个空孩子，则后边遍历到的所有节点均不可能有孩子，如果有孩子，直接返回false。

    public static boolean isCBT(Node head) {
        if(head == null) return true;
        boolean flag = false;    // 标记是否开启叶子节点模式
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        Node l = null;
        Node r = null;
        while(!queue.isEmpty()){
            head = queue.poll();
            l = head.left;
            r = head.right;
            if((flag && (l != null || r != null)) || (l == null && r != null)){
                return false;
            }
            if(l != null){
                queue.add(l);
            }
            if(r != null){
                queue.add(r);
            }
            if(l == null || r == null){
                //只要右一个为空，则开启叶子节点模式
                flag = true;
            }
        }
        return true;
    }

判断一棵树是否是平衡二叉树（AVL —— Balance Binary Tree）

平衡二叉树（AVL）：左子树和右子树的高度差不会大于1
思路：递归，分别求出左右子树是否是AVL，并计算出他们的高度，然后比较左右子树的高度即可得出当前的树是否是平衡二叉树。
又是一个典型的树形DP问题


    public class ResultData{
        boolean isAvl;
        int h;
        
        // 常见构造器
        public ResultData(boolean isAvl, int h){
            this.isAvl = isAvl;
            this.h  = h;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return process(root).isAvl;
    }

    private ResultData process(TreeNode root){
        if(root == null) return new ResultData(true,0);   // 空树的高度为0
        // 分别计算出左右子树的计算结果
        ResultData left = process(root.left);
        ResultData right = process(root.right);
        
        if(left.isAvl && right.isAvl && Math.abs(left.h - right.h) < 2){
            return new ResultData(true,Math.max(left.h,right.h) + 1);
        }else{
            return new ResultData(false,0);
        }
    }

求完全二叉树的节点个数

LeeCode222. 完全二叉树的节点个数

思路一：根据完全二叉树的性质求解。

首先计算出此完全二叉树的高度：一直向左孩子搜索，直到左孩子为空
然后计算右子树的高度：方法同上
比较两个二叉树的高度，如果当前的二叉树的高度等于右子树高度+1，则左子树一定为满二叉树，直接累加出节点数，然后去计算右子数
如果当前树的高度不等于右子树的高度+1,则右子树一定为满二叉树，累加左边的结果即可。

思路二: 直接暴力递归
分别计算左右子树的节点总数，然后加上当前节点的1，这种方法，适合任意类型的二叉树求和。

    // 思路一： 直接上暴力递归
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int ans = 1;
        ans += countNodes(root.left);
        ans += countNodes(root.right);
        return ans;
    }


    // 思路二： 根据二叉树的性质求解
    public int countNodes(TreeNode root) {      
        if(root == null) return 0;
        int ans = 0;
        int left = getH(root);         // 求出当前树的高度
        int right = getH(root.right);  // 求出右子树的高度
        if(left == right + 1){
            // 如果当前树的高度比右子树高度高1，则左子树为满二叉树
            ans += (1 << (right)) + countNodes(root.right); 
        }else{
            // 如果当前树的高度不等于右子树高度+1，则右子树为满二叉树
            ans += (1 << (right)) + countNodes(root.left);
        }
        return ans;
    }
    
    
    // 给定一个头节点，计算出该完全二叉树的高度
    private int getH(TreeNode root){
        if(root == null) return 0;
        TreeNode cur = root;
        int ans = 0;
        while(cur != null){
            ans++;
            cur = cur.left;
        }
        return ans;
    }

数据结构——树

树结构基础

入门——实现二叉树的前序、中序、后序遍历（递归、非递归，mirros方法）

查找后继节点

二叉树的序列化和反序列化

按照前序遍历的顺序进行序列化二叉树 ————递归实现

按照层次遍历的顺序进行序列化二叉树————非递归实现

各种二叉树的识别汇总

判断一颗树是否是搜索二叉树（BST —— Binary Search Tree）

判断一棵树是否是完全二叉树（CBT —— Complete Binary Tree））

判断一棵树是否是平衡二叉树（AVL —— Balance Binary Tree）

求完全二叉树的节点个数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读