526互联

p5两链表相交问题和二叉树

发布时间 2023-08-12 09:52:17作者: 无聊的飞熊

（本文大多从杀戒之声处来，就想着自己方便看）

两链表相交问题

所谓相交，是指两链表有某一内存地址相同，则为相交，

判断有环无环，

  • 哈希表（set），第一次相同（单向链表）

  • 快慢指针，快走2，慢走1，快慢指针第一次相遇后，将快指针返回头节点，慢指针不动，快改为走1，看快慢节点是否能相遇，有环则一定会在入环节点相遇

package ZuoShen.Class04;
​
public class FindFirstIntersectNode {
    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
//
//        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);
​
        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
​
        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);
​
        // 0->9->8->6->7->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);
    }
    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1==null||head2==null){
            return null;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if(loop1==null&&loop2==null){
            return noloop(head1,head2);
        }
        if(loop1!=null&&loop2!=null){
            return bothLoop(head1,loop1,head2,loop2);
        }
        return null;  //一个有环一个无环则直接Null 因为不可能相交
    }
​
    //获取入环节点 如果无环返回null
    public static Node getLoopNode(Node head) {
        if(head==null||head.next==null||head.next.next==null){
            return null;   //至少得三个元素才能构成环
        }
        Node fast=head.next.next;
        Node slow=head.next;
        while (slow!=fast){
            if(fast.next==null||fast.next.next==null){
                return null;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        //此时fast和slow在同一个位置上
        fast=head;
        while (fast!=slow){   //将其中一个节点放到头上，然后一步一步走，再次相遇就是入环节点。
            slow=slow.next;   //这里好像是数学推论
            fast=fast.next;
        }
        return fast;
    }
    //两个链表都是无环的情况
    public static Node noloop(Node head1,Node head2){
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;  //代表链表1长度-链表2长度 可以节约变量
        while (cur1.next!=null){
            n++;
            cur1=cur1.next;
        }
        while (cur2.next!=null){
            n--;
            cur2=cur2.next;
        }
        if(cur1!=cur2){ //当两个的结尾节点内存地址不相等时，说明该无环链表不可能相交
            return null;
        }
        cur1 = n>0?head1:head2;    //长的放在cur1
        cur2 = cur1==head1?head2:head1; //另一个放在cur2
        n=Math.abs(n);
        while (n!=0){
            n--;
            cur1=cur1.next;
        }
        while (cur1!=cur2){
            cur1=cur1.next; //走到最后还不相等就会都走到null,会跳出循环因为都是null
            cur2=cur2.next;
​
        }
        return cur1;
    }
    //两个链表都是有环的情况
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        //此时分3种，两个有环链表不相交；相交且入环节点相同；相交且入环节点不同
        //首先第二种
        if(loop1==loop2){
            Node cur1 = head1;
            Node cur2 = head2;
            int n = 0;
            while (cur1 != loop1) {
                cur1=cur1.next;
                n++;
            }
            while (cur2 != loop2) {
                cur2=cur2.next;
                n--;
            }
            cur1 = n>0?head1:head2;
            cur2 = cur1==head1?head2:head1;
            n = Math.abs(n);
            while (n!=0){
                cur1=cur1.next;
                n--;
            }
            while (cur1!=cur2){
                cur1=cur1.next;
                cur2=cur2.next;
            }
            return cur1;
        }else {
            //此时为情况1和情况3
            Node cur1 = loop1.next;
            while (cur1!=loop1){
                if(cur1==loop2){
                    return loop1; //情况3  随便返回一个都行
                }
                cur1=cur1.next;
            }
            return null;  //情况1  loop1走了一圈发现没有loop2 说明没相交
        }
    }
}

二叉树的递归序

 
 
 
 
 
 
 
1
2
3
4
5
6
7
 

1，2，4，4，4，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1 相当于第一次到自己的时候输出一下，然后左子树走完后输出一下，右子树走完后输出一下。这是递归实现，所有的递归都可以用非递归替代。1，2，4，4，4，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1 相当于第一次到自己的时候输出一下，然后左子树走完后输出一下，右子树走完后输出一下。这是递归实现，所有的递归都可以用非递归替代。

public static void diguixu{
if(head == null){
return;
    }
    digui(head.left);
    digui(head.right);
}

先序遍历（头左右）：1，2，4，5，3，6，7 相当于递归序里第一次来到的时候打印，第二三次到的时候什么也不做

中序遍历（左头右）：4，2，5，1，6，3，7 相当于递归序里第二次来到的时候打印，第一三次到的时候什么也不做

后序遍历（左右头）：4，2，5，1，6，3，7 相当于递归序里第三次来到的时候打印，第一二次到的时候什么也不做

用栈实现：

先序遍历（头左右）：压入根节点 相当于深度优先遍历

  1. 从栈中弹出一个节点cur

  2. 打印（处理）cur

  3. 先压右再压左（如果有）

  4. 循环上面3步

后序遍历（左右头）:

方法一：

  1. 从栈中弹出一个节点cur并将其放入收集栈中

  2. 先压左再压右（如果有）

  3. 循环上面2步

    最后收集栈中依次弹出打印就是后序遍历

方法二：

先看栈顶元素有无左孩子，有就入栈，这里完成左边界入栈。然后从栈顶peek，如果该节点没有左右孩子，则pop掉并打印，并且将该元素赋给变量h，再peek栈顶元素，这个节点因为是h的父元素，所以看有没有右孩子，如果有，将右孩子压入栈。将该节点右孩子处理完后，此节点被pop，以此类推。

中序遍历（左头右）：

  1. 每棵子树左边界进栈

  2. 依次弹出的时候打印

  3. 如果弹出的节点有右子树，则对该节点的右子树进行上面两步循环

package ZuoShen.Class05;
​
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
​
public class BinaryTreeTraversal {
    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
        // recursive
        System.out.println("==============recursive==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        posOrderRecur(head);
        System.out.println();
​
        // unrecursive
        System.out.println("============unrecursive=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur1(head);
        posOrderUnRecur2(head);
        SequenceTraversal(head);
    }
    //preorder traversal先序遍历  recursive 递归的
    public static void preOrderRecur(Node head) {
        if(head==null){
            return;
        }
        System.out.print(head.value+" ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
    //inorder traversal中序遍历
    public static void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.value + " ");
        inOrderRecur(head.right);
    }
    //postorder traversal后序遍历
    public static void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value + " ");
    }
    public static void preOrderUnRecur(Node head) {
        //先右后左存入栈，弹出时打印
        System.out.print("pre-order: ");
        if (head!=null){
            Stack<Node> nodes = new Stack<>();
            nodes.push(head);
            while (!nodes.empty()){
                head=nodes.pop();
                System.out.print(head.value + " ");
                if(head.right!=null){
                    nodes.push(head.right);
                }
                if(head.left!=null){
                    nodes.push(head.left);
                }
            }
        }
        System.out.println();
    }
    public static void inOrderUnRecur(Node head) {
        //用null判断
        //先把左边界压入至null，然后如果是null，弹出栈顶，打印，将该元素的右孩子赋给变量继续循环
        System.out.print("in-order: ");
        if(head!=null){
            Stack<Node> nodes = new Stack<>();
            while (!nodes.empty()||head!=null){
                if(head!=null){
                    nodes.push(head);
                    head=head.left;
                }else {
                    head=nodes.pop();
                    System.out.print(head.value + " ");
                    head=head.right;
                }
            }
        }
        System.out.println();
    }
        public static void posOrderUnRecur1(Node head) {
        //用先左后右进栈，弹出存入收集栈 再弹出收集栈
        System.out.print("pos-order: ");
        if (head!=null){
            Stack<Node> nodes = new Stack<>();
            Stack<Node> collect = new Stack<>();
            nodes.push(head);
            while (!nodes.empty()){
                head=nodes.pop();
                collect.push(head);
                if(head.left!=null){
                    nodes.push(head.left);
                }
                if(head.right!=null){
                    nodes.push(head.right);
                }
            }
            var a = collect.iterator();
            while (a.hasNext()){
                System.out.print(collect.pop().value+" ");
            }
        }
        System.out.println();
    }
    public static void posOrderUnRecur2(Node head) {
        //用是否为左右子树判断
        //不用收集栈的后序遍历，先存入左边界，再peek 比较复杂
        System.out.print("pos-order: ");
        if (head != null) {
            Stack<Node> nodes = new Stack<>();
            nodes.push(head);
            Node c = null;
            while (!nodes.empty()){
                c = nodes.peek();
                if(c.left!=null&&head!=c.left&&head!=c.right){
                    //用于控制只将左边界传入 并且head!=c.left控制不去重复压栈 head!=c.right控制别理右子树
                    nodes.push(c.left);
                }else if(c.right!=null&&head!=c.right){
                    //当树从最左下方往上走时，如果有右子树则压栈，并且head!=c.right控制不去重复压栈
                    nodes.push(c.right);
                }else {
                    System.out.print(nodes.pop().value+" ");
                    head=c; //控制别再重复压栈
                }
            }
        }
        System.out.println();
    }
}
class Node{
    public int value;
    public Node left;
    public Node right;
    Node(int value){
        this.value = value;
    }
}

打印二叉树

将中序遍历倒过来，右头左，递归遍历的时候传入高度、符号、节点、长度。将长度填补为17位、右子树是'v'，左子树是'^'，高度作用：假如是第三层的节点，需要先打印2*17个空格。

package ZuoShen.Class05;
​
public class PrintBinaryTree {
    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);
    }
}

宽度优先遍历（层序遍历）

用队列，先进先出，头进尾出，放入头结点，弹出然后打印，先进左再进右（如果有的话），出来的时候直接打印再先进左再进右。（类似于后序遍历装入收集栈的操作）

代码实现：

    public static void SequenceTraversal(Node head){
        //层序遍历
        Queue<Node> nodes = new LinkedList<>();
        if(head!=null){
            nodes.add(head);
            while (!nodes.isEmpty()){
                head = nodes.poll();
                System.out.print(head.value+" ");
                if(head.left!=null){
                    nodes.add(head.left);
                }
                if(head.right!=null){
                    nodes.add(head.right);
                }
            }
        }
        System.out.println();
    }

找到树的最大宽度

方法一：通过宽度优先遍历实现，其中有队列，利用一个map存储将节点作为Key，所在层数作为value，设置变量当前层数、当前节点数、最大宽度，每次poll出节点时判断该节点层数与当前层数是否一致，来决定更新。

方法二：不需要map，但是需要队列。

方法三：层序遍历

package ZuoShen.Class05;
​
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
​
public class TreeMaxWidth {
    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.left.left.right = new Node(3);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
        System.out.println(getMaxWidth1(head));
        System.out.println(getMaxWidth2(head));
        System.out.println(getMaxWidth3(head));
    }
​
    public static int getMaxWidth1(Node head){
        //方法一  用哈希表完成
        Queue<Node> nodes = new LinkedList<>();
        HashMap<Node,Integer> map = new HashMap<>();
        nodes.add(head);
        map.put(head,1);
        int curlevel = 1;
        int curNodeNum = 0;
        int max=Integer.MIN_VALUE;
        if(head!=null){
            while (!nodes.isEmpty()){
                head=nodes.poll();
                if(map.get(head)==curlevel){
                    curNodeNum++;
                }else {
                    max=Math.max(max,curNodeNum);
                    curNodeNum=1;
                    curlevel++;
                }
                if(head.left!=null){
                    nodes.add(head.left);
                    map.put(head.left,curlevel+1);
                }
                if(head.right!=null){
                    nodes.add(head.right);
                    map.put(head.right,curlevel+1);
                }
            }
        }
        return Math.max(max,curNodeNum);
    }
    public static int getMaxWidth2(Node head){
        //方法二：不用Hashmap只用队列，再加上max、curNode、head、curnum、curendNode四个变量
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(head);
        Node curendNode = head;//当前层的最后一个
        Node curNode = null;   //当前节点
        int curnum = 0;//当前层数量
        int max = Integer.MIN_VALUE;
        while (!nodes.isEmpty()){
            head=nodes.poll();  //head用于遍历
            if(head.left!=null){
                nodes.add(head.left);
                curNode=head.left;  //curNode用于记录新进队列的节点
            }
            if(head.right!=null){
                nodes.add(head.right);
                curNode=head.right;
            }
            curnum++;
            if(head==curendNode){
                max=Math.max(max,curnum);
                curnum=0;
                curendNode=curNode; //将最新进入队列的节点作为当前层的尾部
                curNode=null;
            }
        }
        return max;
    }
    public static int getMaxWidth3(Node head){
        //方法三：层序遍历
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(head);
        int max = Integer.MIN_VALUE;
        int curSize; //当前层的大小
        while (!nodes.isEmpty()){
            curSize=nodes.size();
            max=Math.max(max,curSize);
            for (int i = 0; i < curSize; i++) {//重点在于这个for循环次数为size大小，因此上一层的一定会被全部弹出
                head=nodes.poll();              //下一层的全部进入  然后重新计算size
                if(head.left!=null){
                    nodes.add(head.left);
                }
                if(head.right!=null){
                    nodes.add(head.right);
                }
            }
        }
        return max;
    }
}