【算法&数据结构体系篇class10、11】：二叉树

妖狐艹你老母 2024-03-26 15:40 64阅读 0赞

### 一、二叉树的先序、中序、后序遍历 ###

> 先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树  
>   
> 中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树  
>   
> 后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点

### 二、递归方式实现二叉树的先序、中序、后序遍历 ###

> 1）理解递归序  
> **能回到节点处3次**  
> 2）先序、中序、后序都可以在递归序的基础上加工出来  
>   
> 3）**第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序**

**代码演示：**

package class10;
    
    /**
     * 递归方式：先序 中序 后序 打印二叉树
     */
    public class RecursiveTraversalBT {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int v) {
                value = v;
            }
        }
    
        //先序打印全部节点  根左右
        public static void pre(Node head) {
            if (head == null) return;
            System.out.println(head.value);
            pre(head.left);
            pre(head.right);
        }
    
        //中序打印全部节点  左根右
        public static void in(Node head) {
            if (head == null) return;
            in(head.left);
            System.out.println(head.value);
            in(head.right);
        }
    
        //后序打印全部节点 左右根
        public static void pos(Node head) {
            if (head == null) return;
            pos(head.left);
            pos(head.right);
            System.out.println(head.value);
        }
    
        public static void main(String[] args) {
            Node head = new Node(1);
            head.left = new Node(2);
            head.right = new Node(3);
            head.left.left = new Node(4);
            head.left.right = new Node(5);
            head.right.left = new Node(6);
            head.right.right = new Node(7);
    
            pre(head);
            System.out.println("========");
            in(head);
            System.out.println("========");
            pos(head);
            System.out.println("========");
        }
    }

"D:\Program Files\Java\jdk1.8.0_151\bin\java.exe" "-javaagent:D:\Program Files\JetBrains\IntelliJ IDEA 2019.2.4\lib\idea_rt.jar=63444:D:\Program Files\JetBrains\IntelliJ IDEA 2019.2.4\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_151\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\rt.jar;D:\Java\algorithm\算法和数据结构体系学习班代码\算法和数据结构体系学习班代码\bin" class10.RecursiveTraversalBT
    1
    2
    4
    5
    3
    6
    7
    ========
    4
    2
    5
    1
    6
    3
    7
    ========
    4
    5
    2
    6
    7
    3
    1
    ========
    
    Process finished with exit code 0

### 三、X节点的祖先节点 交集 ###

> X节点的祖先节点 交集  
> **先序遍历顺序在X之前的节点 ∩ 后序遍历顺序在X之后的节点**  
>   
> 1.先序遍历是根左右，祖先节点都是在排在前面的后续遍历是左右根，祖先节点都是排在后面的 所以是两次遍历的交集节点。就是祖先节点  
> 2.X的孩子节点不会出现在该交集中，先序遍历根左右 孩子节点是排在后面的 不在该交集  
> 3.X作为左树，它的右兄弟节点不会出现该交集中。先序遍历根左右，右兄弟节点都是在后面，所以不会再该交集  
> 4.X作为右树，它的左兄弟节点不会出现该交集中，后序遍历左右根，左兄弟节点都是再前面，所以不会在该交集  
> 全部节点类型判断分析结束  
> 至此，证明先序遍历顺序在X之前的节点 ∩ 后序遍历顺序在X之后的节点 两者交集的节点 就是X祖先节点  
>

### 四、非递归方式实现二叉树的先序、中序、后序遍历 ###

> 1）任何递归函数都可以改成非递归  
>   
> 2）自己设计压栈的来实现

**代码演示：**

package class10;
    
    import java.util.Stack;
    
    
    /**
     * 非递归方式：先序 中序 后序 打印二叉树
     */
    public class UnRecursiveTraversalBT {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int v) {
                value = v;
            }
        }
    
        //先序 利用栈结构，遍历入栈，先打印，在入右节点 再入左节点，这样出栈才是左在右前面
        public static void pre(Node head){
            System.out.print("pre-order: ");
            if(head != null){
                Stack<Node> stack = new Stack<>();
                //头节点先入栈
                stack.push(head);
                while(!stack.isEmpty()){
                    //出头节点 打印
                    head = stack.pop();
                    System.out.print(head.value+" ");
                    //先判断右子树非空 则入栈右子树，再去判断左子树且入栈
                    if(head.right !=null){
                        stack.push(head.right);
                    }
                    if(head.left !=null){
                        stack.push(head.left);
                    }
                }
            }
            System.out.println();
        }
    
    
        //中序 先遍历左子树节点都入栈直到null，就弹出，再指向右子树，右子树再遍历完它的左子树入栈 再弹出
        public static void in(Node cur){
            System.out.print("in-order: ");
            if(cur != null){
                Stack<Node> stack = new Stack<>();
                while(!stack.isEmpty() || cur != null){
                    //1.当前节点非空，节点入栈，并往左子树下沉，直到左子树为空
                    if(cur != null){
                        stack.push(cur);
                        cur = cur.left;
                    }else{
                        //左子树空，那么就弹出其前节点，然后再下沉右子树。
                        //循环去遍历右子树的子节点
                        cur = stack.pop();
                        System.out.print(cur.value + " ");
                        cur = cur.right;
                    }
                }
            }
            System.out.println();
        }
    
        //后序 已知先序是根左右，那么可以先得到根右左，然后再逆序 变成左右根 需要两个栈
        public static void pos1(Node head){
            System.out.print("pos-order: ");
            if(head !=null){
                //建立两个栈，stack1出栈顺序为根右左，然后依次入栈stack2 出栈顺序就逆序变成左右根  中序遍历
                Stack<Node> stack1 = new Stack<>();
                Stack<Node> stack2 = new Stack<>();
                stack1.push(head);
                while(!stack1.isEmpty()){
                    Node node = stack1.pop();
                    stack2.push(node);
                    if(node.left != null){
                        stack1.push(node.left);
                    }
                    if(node.right != null){
                        stack1.push(node.right);
                    }
                }
                //入栈是 根右左  出栈就是左右根
                while (!stack2.isEmpty()){
                    System.out.print(stack2.pop().value+" ");
                }
            }
            System.out.println();
        }
    
        //后序  只用一个栈
        public static void pos2(Node head){
            System.out.print("pos-order: ");
            if(head != null){
                Stack<Node> stack = new Stack<>();
                //栈先入头节点
                stack.push(head);
                //辅助变量cur 存放每次的栈顶节点
                Node cur = null;
                while(!stack.isEmpty()){
                    //取出当前栈顶元素。
                    cur = stack.peek();
                    //判断栈顶元素左节点是否非空 是否左右节点不等于 弹出的上个节点head.
                    if(cur.left!=null && cur.left != head && cur.right != head){
                        //符合则左子节点入栈
                        stack.push(cur.left);
                        //来到右节点判断 非空 且弹出的head节点不等于其右节点。
                    }else if(cur.right != null && cur.right != head){
                        //符合则右节点入栈入栈
                        stack.push(cur.right);
                    }else {
                        //如果左右子节点都为空 或者说head是其cur节点的子节点（这个说明是从下往上倒回去，下面的子节点已经遍历且抛出打印了 不能再入栈）
                        //那就再出栈顶元素，打印 且将head节点赋值为当前出栈的元素，用于上层的cur节点遍历比较
                        cur = stack.pop();
                        System.out.print(cur.value + " ");
                        head = cur;
                    }
                }
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            Node head = new Node(1);
            head.left = new Node(2);
            head.right = new Node(3);
            head.left.left = new Node(4);
            head.left.right = new Node(5);
            head.right.left = new Node(6);
            head.right.right = new Node(7);
    
            pre(head);
            System.out.println("========");
            in(head);
            System.out.println("========");
            pos1(head);
            System.out.println("========");
            pos2(head);
            System.out.println("========");
        }
    }

"D:\Program Files\Java\jdk1.8.0_151\bin\java.exe" "-javaagent:D:\Program Files\JetBrains\IntelliJ IDEA 2019.2.4\lib\idea_rt.jar=63453:D:\Program Files\JetBrains\IntelliJ IDEA 2019.2.4\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_151\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\rt.jar;D:\Java\algorithm\算法和数据结构体系学习班代码\算法和数据结构体系学习班代码\bin" class10.UnRecursiveTraversalBT
    pre-order: 1 2 4 5 3 6 7 
    ========
    in-order: 4 2 5 1 6 3 7 
    ========
    pos-order: 4 5 2 6 7 3 1 
    ========
    pos-order: 4 5 2 6 7 3 1 
    ========
    
    Process finished with exit code 0

### 五、实现二叉树的按层遍历 ###

1）其实就是宽度优先遍历，用队列

2）可以通过设置flag变量的方式，来发现某一层的结束（看题目）

package class11;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 层序遍历，从上往下 从左往右打印节点
     * 利用队列
     */
    public class LevelTraversalBT {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int v) {
                value = v;
            }
        }
    
        //层序遍历
        public static void level(Node head){
            if(head == null) return;
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            while(!queue.isEmpty()){
                head = queue.poll();
                System.out.println(head.value);
                if(head.left != null){
                    queue.add(head.left);
                }
                if(head.right != null){
                    queue.add(head.right);
                }
            }
        }
    
        public static void main(String[] args) {
            Node head = new Node(1);
            head.left = new Node(2);
            head.right = new Node(3);
            head.left.left = new Node(4);
            head.left.right = new Node(5);
            head.right.left = new Node(6);
            head.right.right = new Node(7);
    
            level(head);
            System.out.println("========");
        }
    }

### 六、实现二叉树的序列化和反序列化 ###

1）先序方式序列化和反序列化

2）按层方式序列化和反序列化

> /\*  
>  \* 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，  
>  \* 以下代码全部实现了。  
>  \* **但是，二叉树无法通过中序遍历的方式实现序列化和反序列化**  
>  \* **因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。**  
>  \* 比如如下两棵树  
>  \* \_\_2  
>  \* /  
>  \* 1  
>  \* 和  
>  \* 1\_\_  
>  \* \\  
>  \* 2  
>  \* 补足空位置的中序遍历结果都是\{ null, 1, null, 2, null\}  
>  \*   
>  \* \*/

package class11;
    
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 序列化：将二叉树结构序列化成字符串，这里用集合保存字符串
     * 表示将内存的数据结构给保存到硬盘中，长期保存 转换成字节或字符
     * 反序列化：将序列化后的字符集合反序列回 二叉树结构， 再恢复原结构到内存中
     */
    public class SerializeAndReconstructTree {
        /*
         * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
         * 以下代码全部实现了。
         * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
         * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
         * 比如如下两棵树
         *         __2
         *        /
         *       1
         *       和
         *       1__
         *          \
         *           2
         * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
         *
         * */
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        //先序遍历方式实现序列化
        public static Queue<String> preSerial(Node head) {
            //定义字符串型队列保存每个二叉树节点
            Queue<String> ans = new LinkedList<>();
            //先序遍历
            pres(head, ans);
            return ans;
        }
    
        public static void pres(Node head, Queue<String> ans) {
            //为空，则添加null,空位置注意一定要填充位置，否则还原二叉树会有歧义的
            if (head == null) {
                ans.add(null);
            } else {
                //根左右
                ans.add(String.valueOf(head.value));
                pres(head.left, ans);
                pres(head.right, ans);
    
            }
        }
    
        //先序队列实现反序列化，构建二叉树
        public static Node buildByPreQueue(Queue<String> prelist) {
            //如果队列为空或者大小0  直接返回空节点
            if (prelist == null || prelist.size() == 0) {
                return null;
            }
            return preb(prelist);
        }
    
        //队列不为空 那么就进行反序列化 先序序列 构建二叉树
        private static Node preb(Queue<String> prelist) {
            //先弹出节点
            String value = prelist.poll();
            //null则表示空节点，返回null节点
            if (value == null) {
                return null;
            }
            //先序 根左右，先定义当前节点，在定义其左子树  右子树
            Node head = new Node(Integer.valueOf(value));
            head.left = preb(prelist);
            head.right = preb(prelist);
            //返回头节点
            return head;
        }
    
    //    -----------------------------------------------------
    
        //后序遍历方式实现序列化
        public static Queue<String> posSerial(Node head) {
            Queue<String> ans = new LinkedList<>();
            poss(head, ans);
            return ans;
        }
    
        public static void poss(Node head, Queue<String> ans) {
            if (head == null) {
                ans.add(null);
            } else {
                poss(head.left, ans);
                poss(head.right, ans);
                ans.add(String.valueOf(head.value));
            }
        }
    
        //后序队列实现反序列化，构建二叉树
        public static Node buildByPosQueue(Queue<String> poslist) {
            if (poslist == null || poslist.size() == 0) {
                return null;
            }
            //后序遍历队列是 左右根，可以转换为 逆序保存在栈 出栈即，根右左。 便于构建二叉树能返回根节点
            Stack<String> stack = new Stack<>();
            while (!poslist.isEmpty()) {
                //队列入栈
                stack.push(poslist.poll());
            }
            return posb(stack);
        }
    
        //后序遍历队列顺序是 左右根
        public static Node posb(Stack<String> posstack) {
            String value = posstack.pop();
            if (value == null) {
                return null;
            }
            //注意，因为出栈顺序是 根右左，所以先定义根节点，然后在递归其右子树，再是左子树
            Node head = new Node(Integer.valueOf(value));
            head.right = posb(posstack);
            head.left = posb(posstack);
            return head;
        }
    
    //    ----------------------------------------------------------
    
        //层序遍历方式实现序列化   需要额外一个队列辅助保存每层元素按序输出
        public static Queue<String> levelSerial(Node head) {
            Queue<String> ans = new LinkedList<>();
            if (head == null) {
                ans.add(null);
            } else {
                //头非空，结果集合入头节点  辅助队列也入头节点
                ans.add(String.valueOf(head.value));
                Queue<Node> queue = new LinkedList<>();
                queue.add(head);
                while (!queue.isEmpty()) {
                    //辅助队列不为空，则弹出队首，依次遍历左右子节点，非空则再入辅助队列，入结果队列，为空则结果队列入null
                    head = queue.poll();
                    //左子节点非空，那么入结果队列 辅助队列
                    if (head.left != null) {
                        ans.add(String.valueOf(head.left.value));
                        queue.add(head.left);
                    } else {
                        //为空 则入结果队列null
                        ans.add(null);
                    }
                    if (head.right != null) {
                        ans.add(String.valueOf(head.right.value));
                        queue.add(head.right);
                    } else {
                        ans.add(null);
                    }
                }
            }
            return ans;
        }
    
        //层序队列实现反序列化，构建二叉树
        public static Node buildByLevelQueue(Queue<String> levelList) {
            if (levelList == null || levelList.size() == 0) {
                return null;
            }
            //定义一个节点队列，用于进行保存levelList的节点 先保存根节点，后续进行遍历
            Queue<Node> queue = new LinkedList<>();
            Node head = generateNode(levelList.poll());
            //注意判断可能节点是null [null]的情况 避免报空指针
            if (head != null) {
                queue.add(head);
            }
            //辅助节点用来遍历从head开始每一个节点
            Node node = null;
            while (!queue.isEmpty()) {
                //遍历一开始保存了头节点的辅助队列，弹出节点
                node = queue.poll();
                //依次弹出原层序队列节点，就是从上到下从左往右，然后分别构建头节点的左节点 右节点，
                node.left = generateNode(levelList.poll());
                node.right = generateNode(levelList.poll());
                //非空，那么就表示有左子树，左节点入队列，继续下一轮的遍历
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            //最后构建完之后返回head节点
            return head;
        }
    
        //构建节点函数，传入levelList层序队列字符串，为空则返回null节点，不为空则创建新节点返回
        public static Node generateNode(String val) {
            if (val == null) {
                return null;
            }
            return new Node(Integer.valueOf(val));
        }
    
        // for test
        public static Node generateRandomBST(int maxLevel, int maxValue) {
            return generate(1, maxLevel, maxValue);
        }
    
        // for test
        public static Node generate(int level, int maxLevel, int maxValue) {
            if (level > maxLevel || Math.random() < 0.5) {
                return null;
            }
            Node head = new Node((int) (Math.random() * maxValue));
            head.left = generate(level + 1, maxLevel, maxValue);
            head.right = generate(level + 1, maxLevel, maxValue);
            return head;
        }
    
        // for test
        public static boolean isSameValueStructure(Node head1, Node head2) {
            if (head1 == null && head2 != null) {
                return false;
            }
            if (head1 != null && head2 == null) {
                return false;
            }
            if (head1 == null && head2 == null) {
                return true;
            }
            if (head1.value != head2.value) {
                return false;
            }
            return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
        }
    
        // for test
        public static void printTree(Node head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }
    
        public static void printInOrder(Node head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.right, height + 1, "v", len);
            String val = to + head.value + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.left, height + 1, "^", len);
        }
    
        public static String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }
    
        public static void main(String[] args) {
            int maxLevel = 5;
            int maxValue = 100;
            int testTimes = 1000000;
            System.out.println("test begin");
            for (int i = 0; i < testTimes; i++) {
                Node head = generateRandomBST(maxLevel, maxValue);
                Queue<String> pre = preSerial(head);
                Queue<String> pos = posSerial(head);
                Queue<String> level = levelSerial(head);
                Node preBuild = buildByPreQueue(pre);
                Node posBuild = buildByPosQueue(pos);
                Node levelBuild = buildByLevelQueue(level);
                if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("test finish!");
    
        }
    
    
    }

### 七、**Leetcode431. Encode N-ary Tree to Binary Tree** ###

> */\*\* 431leetcode*  
>  *\* // 本题测试链接：* [*https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree*][https_leetcode.com_problems_encode-n-ary-tree-to-binary-tree]  
>  *\* 多叉树转二叉树*  
>  *\* 思路：多叉树就是多个子节点，可以转换二叉树按照这个定义来转换：当前节点的子节点，就依次放到其左子树的右孩子节点*  
>  *\* 比如 0节点 123孩子节点 1节点 45孩子节点，2节点 678孩子节点，3节点 9孩子节点*  
>  *\* 0*  
>  *\* 1 2 3*  
>  *\* 4 5 6 7 8 9*  
>  *\**  
>  *\* 转换二叉树如下：*  
>  *\* 0*  
>  *\* 1*  
>  *\* 4 2*  
>  *\* 5 6 3*  
>  *\* 7 9*  
>  *\* 8*  
>  *\*/*

package class11;
    
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** 431leetcode
     * // 本题测试链接：https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree
     * 多叉树转二叉树
     * 思路：多叉树就是多个子节点，可以转换二叉树按照这个定义来转换：当前节点的子节点，就依次放到其左子树的右孩子节点
     *       比如 0节点 123孩子节点 1节点 45孩子节点，2节点 678孩子节点，3节点 9孩子节点
     *       0
     *    1    2      3
     * 4  5   6 7 8    9
     *
     * 转换二叉树如下：
     *           0
     *       1
     *    4         2
     *      5   6         3
     *            7     9
     *              8
     */
    public class EncodeNaryTreeToBinaryTree {
        // 提交时不要提交这个类
        public static class Node {
            public int val;
            public List<Node> children;
    
            public Node() {
            }
    
            public Node(int _val) {
                val = _val;
            }
    
            public Node(int _val, List<Node> _children) {
                val = _val;
                children = _children;
            }
        };
    
        // 提交时不要提交这个类
        public static class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
    
            TreeNode(int x) {
                val = x;
            }
        }
    
        class Codec {
            //多叉树转二叉树
            public TreeNode encode(Node root){
                if(root == null){
                    return null;
                }
                //非空，当前多叉树的root节点为根节点，可先将其赋值给二叉树根节点
                TreeNode head = new TreeNode(root.val);
                //转换成二叉树，可以定义其多叉树的每个节点的孩子节点都转换成当前节点的左子树，并且依次放在左子树的右节点，形成一个右树形式
                head.left = en(root.children);
                return head;
            }
            public TreeNode en(List<Node> children){
                //定义两个辅助节点变量进行递归
                TreeNode head = null;
                TreeNode cur = null;
                for(Node child:children){
                    //获取当前孩子节点的值，并创建对应的二叉树节点
                    TreeNode tNode = new TreeNode(child.val);
                    //头为空，比如第一次进入那么就将当前节点赋值head
                    if(head == null){
                        head =tNode;
                    }else{
                        //如果为空，说明已经遍历了第一个孩子节点 就将当前cur的右指针指向下个孩子节点。 即将同层的孩子节点都形成一个右树
                        cur.right = tNode;
                    }
                    //这里cur辅助变量 来表示当前遍历到哪个节点
                    cur = tNode;
                    //接着往左递归。看该节点是否有孩子节点 继续处理该节点的孩子节点 再递归回上层处理
                    cur.left = en(child.children);
                }
                return head;
            }
    
            //二叉树转多叉树
            public Node decode(TreeNode root){
                if(root == null){
                    return null;
                }
                //非空 创建一个多叉树，节点为当前二叉树根节点，孩子节点是根节点的左树，左树进行递归完善底层的结构
                return new Node(root.val,de(root.left));
            }
            public  List<Node> de(TreeNode root){
                //定义一个当前节点的孩子节点集合。来返回当前节点的孩子节点
                List<Node> children = new ArrayList<>();
                if(root != null){
                    //当根节点不为空，继续往左子树创建多叉树的节点cur,表示每个树根节点的孩子节点
                    Node cur = new Node(root.val,de(root.left));
                    //加入集合，然后遍历的二叉树节点要往右沉，往右的是同层孩子节点，添加之前还会递归去处理右节点自己的子树
                    children.add(cur);
                    root = root.right;
                }
                //最后返回根的孩子节点。
                return children;
            }
    
    
        }
    
    }

### 八、如何设计一个打印整棵树的打印函数 ###

package class11;
    
    /**
     * 打印二叉树
     *
     * H1H根节点 第一排
     * V1v 表示左边一排下方离我最近的跟我连接
     * ^1^ 表示左边一排上方理我最近的跟我连接
     */
    public class Code04_PrintBinaryTree {
    
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static void printTree(Node head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }
    
        public static void printInOrder(Node head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.right, height + 1, "v", len);
            String val = to + head.value + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.left, height + 1, "^", len);
        }
    
        public static String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }
    
        public static void main(String[] args) {
            Node head = new Node(1);
            head.left = new Node(-222222222);
            head.right = new Node(3);
            head.left.left = new Node(Integer.MIN_VALUE);
            head.right.left = new Node(55555555);
            head.right.right = new Node(66);
            head.left.left.right = new Node(777);
            printTree(head);
    
            head = new Node(1);
            head.left = new Node(2);
            head.right = new Node(3);
            head.left.left = new Node(4);
            head.right.left = new Node(5);
            head.right.right = new Node(6);
            head.left.left.right = new Node(7);
            printTree(head);
    
            head = new Node(1);
            head.left = new Node(1);
            head.right = new Node(1);
            head.left.left = new Node(1);
            head.right.left = new Node(1);
            head.right.right = new Node(1);
            head.left.left.right = new Node(1);
            printTree(head);
    
        }
    
    }

"D:\Program Files\Java\jdk1.8.0_151\bin\java.exe" "-javaagent:D:\Program Files\JetBrains\IntelliJ IDEA 2019.2.4\lib\idea_rt.jar=59499:D:\Program Files\JetBrains\IntelliJ IDEA 2019.2.4\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_151\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_151\jre\lib\rt.jar;D:\Java\algorithm\算法和数据结构体系学习班代码\算法和数据结构体系学习班代码\bin" class11.Code04_PrintBinaryTree
    Binary Tree:
                                            v66v       
                            v3v       
                                         ^55555555^    
           H1H       
                       ^-222222222^   
                                                             v777v      
                                        ^-2147483648^  
    
    Binary Tree:
                                             v6v       
                            v3v       
                                             ^5^       
           H1H       
                            ^2^       
                                                              v7v       
                                             ^4^       
    
    Binary Tree:
                                             v1v       
                            v1v       
                                             ^1^       
           H1H       
                            ^1^       
                                                              v1v       
                                             ^1^       
    
    
    Process finished with exit code 0

看结果例子：

> *\* H1H根节点 第一排*  
> *\* V1v 表示左边一排下方离我最近的跟我连接*  
> *\* ^1^ 表示左边一排上方理我最近的跟我连接*

顺时针旋转90度。就是实际二叉树结构

![c55251c64ecef239921a475689519e22.png][]

### 九、求二叉树最宽的层有多少个节点 ###

package class11;
    
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * 求二叉树最宽的层有多少个节点
     */
    public class TreeMaxWidth {
    
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        //方法一：利用哈希表存储每个节点所在层数，同步每层的节点，保存最大值
        public static int maxWidthUseMap(Node head) {
            if (head == null) {
                return 0;
            }
            //定义队列，保存节点，进行层序遍历
            Queue<Node> queue = new LinkedList<>();
            queue.add(head);
            //定义哈希表，先保存头节点，所在层数在第一层
            HashMap<Node,Integer> map = new HashMap<>();
            map.put(head,1);
            //定义变量 当前层、当前层的节点个数、最大层节点个数
            int curLevel = 1;
            int curLevelNodes = 0;
            int max = 0;
            while(!queue.isEmpty()){
                //队列弹出节点，并获取该节点的层数
                Node cur = queue.poll();
                int curNodeLevel = map.get(cur);
                //如果节点的左右节点非空，那么就将子节点入队列，然后添加到哈希表，层数就是当前层数+1
                if(cur.left != null){
                    queue.add(cur.left);
                    map.put(cur.left,curNodeLevel+1);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                    map.put(cur.right,curNodeLevel+1);
                }
                //如果当前节点层数与当前遍历的所在层数相等，那么当前层数+1
                if(curNodeLevel == curLevel){
                    curLevelNodes++;
                }else{
                    //不同层，说明就来到了下一层，刷新目前最大值层数个数， 层数+1，当前层数归1
                    max = Math.max(max,curLevelNodes);
                    curLevel++;
                    curLevelNodes = 1;
                }
            }
            //最后退出 最后一层是curLevelNode++直到空退出，没有进行最大值判断，最后需要最大值
            max = Math.max(max,curLevelNodes);
            return max;
        }
    
        //方法二：不用哈希表，有限辅助节点变量 主要就是保存当前层末节点和下一层的末节点
        public static int maxWidthNoMap(Node head){
            if(head == null){
                return 0;
            }
            Queue<Node>queue = new LinkedList<>();
            queue.add(head);
            //辅助变量 当前层末节点、下一层末节点、当前层节点数、层数最大值
            Node curEnd = head;
            Node nextEnd = null;
            int curLevelNodes = 0;
            int max = 0;
            while(!queue.isEmpty()){
                //弹出队列节点，当前节点左右节点非空，那么就子节点入队列，并且刷新nextEnd节点
                Node cur = queue.poll();
                if(cur.left != null){
                    queue.add(cur.left);
                    nextEnd = cur.left;
                }
                if(cur.right != null){
                    queue.add(cur.right);
                    nextEnd = cur.right;
                }
                //刷新当前节点数+1
                curLevelNodes++;
                //如果当前节点来到了当前层的末节点 那么就要下移到下一层
                if(cur == curEnd){
                    //刷新以往层的最大值,
                    max = Math.max(max,curLevelNodes);
                    //当前层节点清空
                    curLevelNodes = 0;
                    //然后要将下一层的末节点给到curEnd当前层
                    curEnd = nextEnd;
                }
            }
            return max;
        }
    
        // for test
        public static Node generateRandomBST(int maxLevel, int maxValue) {
            return generate(1, maxLevel, maxValue);
        }
    
        // for test
        public static Node generate(int level, int maxLevel, int maxValue) {
            if (level > maxLevel || Math.random() < 0.5) {
                return null;
            }
            Node head = new Node((int) (Math.random() * maxValue));
            head.left = generate(level + 1, maxLevel, maxValue);
            head.right = generate(level + 1, maxLevel, maxValue);
            return head;
        }
    
        public static void main(String[] args) {
            int maxLevel = 10;
            int maxValue = 100;
            int testTimes = 1000000;
            for (int i = 0; i < testTimes; i++) {
                Node head = generateRandomBST(maxLevel, maxValue);
                if (maxWidthUseMap(head) != maxWidthNoMap(head)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
    
        }
    }

### 十、给你二叉树中的某个节点，返回该节点的后继节点 ###

> 二叉树结构如下定义：  
> Class Node \{   
>  Vvalue;  
>  Nodeleft;  
>  Noderight;  
>  Nodeparent;  
> \}  
> 给你二叉树中的某个节点，返回该节点的后继节点

### 十一、折纸条问题，折N次，展开后从上到下打印折痕顺序 ###

> 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。   
> 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。   
> 例如:N=1时，打印:down N=2时，打印: down down up

图例：

![d54f3c49009ce9188ab4e62116675adc.png][]

代码演示：

package class11;
    
    /**
     * 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
     * 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。
     * 例如:N=1时，打印: down N=2时，打印: down down up
     */
    public class PaperFolding {
        public static void printAllFolds(int N) {
            //递归调用程序。 中序遍历，初始默认在第一层，N层，第一层的折痕是下折痕，赋值true
            process(1, N, true);
            System.out.println();
        }
    
        // 当前你来了一个节点，脑海中想象的！
        // 这个节点在第i层，一共有N层，N固定不变的
        // 这个节点如果是凹的话，down = T
        // 这个节点如果是凸的话，down = F
        // 函数的功能：中序打印以你想象的节点为头的整棵树！
        public static void process(int i, int N, boolean down) {
            if (i > N) {
                //假如层数越界了，那么就退出
                return;
            }
    
            //折痕的特点是，每一次都会在当前已有的每个折痕的上下边分别多出 下折痕与上折痕,该特点可以用二叉树表示，第一次折痕为根节点，第二次生成的折痕是第二层节点...
            //下折痕，我们则定义true 上折痕 我们定义false
            //其折痕特征从上往下就是一个二叉树的中序遍历  左中右，左节点折痕就是下折痕，右节点就是上折痕
            //明确的规则：根节点是凹，左子树的根节点是凹，右子树的根节点是凸
            process(i + 1, N, true);
            System.out.print(down == true ? "凹 " : "凸 ");
            process(i + 1, N, false);
        }
    
    
        public static void main(String[] args) {
            int N = 3;
            printAllFolds(N);
        }
    }

[https_leetcode.com_problems_encode-n-ary-tree-to-binary-tree]: https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree
[c55251c64ecef239921a475689519e22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/3db2294021df49d4bfeb526e5821a5d8.png
[d54f3c49009ce9188ab4e62116675adc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/19ee6784c68c4ea28a77eb9b79b4d858.png