java算法题 之 树结构

• • 前中后横向遍历非递归实现
  • 计算树每一层的最多节点个数
  • 判断是搜索二叉树（套路题）
  • 判断是完全二叉树
  • 判断是满二叉树（套路题）
  • 判断是平衡树（套路题）
  • 树结构转成链表（套路题）
  • 子搜索二叉树的节点个数（套路题）
  • • 节点个数
    • 返回子最大搜索树的根节点
  • 树节点最远距离（套路题）
  • 最大快乐值（套路题）
  • 树的个数
  • 查找树中两个节点的最近共父类节点
  • 查找后继结点
  • 折纸凹凸问题
  • 前中序推后序遍历
  • 哈夫曼最小代价问题

package Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Node root=new Node(0);
        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        Node node4=new Node(4);
        Node node5=new Node(5);
        root.left=node1;
        root.right=node2;
        node1.left=node3;
        node1.right=node4;
        node4.right=node5;
        Tree.pre(root);
        System.out.println();
        Tree.inOrderUnRecur(root);
        System.out.println();
        Tree.posOrderUnRecur1(root);
        System.out.println();
        Tree.posOrderUnRecur2(root);

    }
}
class Tree{
    //前序遍历
    public static void pre(Node root){
        System.out.print("pre-order: ");
        if (root==null)return;
        Stack stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node n=stack.pop();
            System.out.print(n.value+" ");
            if (n.right!=null){
                stack.push(n.right);
            }
            if (n.left!=null){
                stack.push(n.left);
            }
        }
    }
    //中序遍历
    public static void inOrderUnRecur(Node head) {
        System.out.print("in-order: ");
        if (head != null) {
            Stack stack = new Stack();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {//向左搜索压入栈中，向右不入栈
                    stack.push(head);
                    head = head.left;
                } else {//持续搜索右树
                    head = stack.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 s1 = new Stack();
            Stack s2 = new Stack();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

    //后序遍历
    public static void posOrderUnRecur2(Node h) {
        System.out.print("pos-order: ");
        if (h != null) {
            Stack stack = new Stack();
            stack.push(h);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }
    //横向遍历
    public static void w(Node root){
        if (root==null)return;
        Deque deque=new ArrayDeque();
        deque.add(root);
        while (!deque.isEmpty()){
            Node n=deque.poll();
            System.out.println(n);
            if (n.left!=null){
                deque.add(n.left);
            }
            if (n.right!=null){
                deque.add(n.right);
            }
        }
    }

}
class Node{
    int value;
    Node left;
    Node right;
    public Node(int num){
        this.value=num;
    }
}

class Tree{
    //基于横向遍历
    public static int fun_1(Node root) {
        if (root == null) return 0;
        Deque deque = new ArrayDeque();
        HashMap map = new HashMap();
        deque.add(root);
        int floor=1;//运行的这一层是哪一层
        int thisNum=0;//本层节点个数
        int maxNum = 0;//每一层最大的值
        map.put(root,floor);
        while (!deque.isEmpty()) {
            Node n = deque.poll();
            if (map.get(n)==floor){//如果还是这一层
                thisNum++;
            }else {//如果和上一层不一层了
                maxNum=Math.max(maxNum,thisNum);
                thisNum=1;//因为已经删除了该层一个元素，所以初始化为1
                floor++;//进行下一层
            }
            if (n.left != null) {
                deque.add(n.left);//进入队列
                map.put(n.left,floor+1);//记录该元素层数
            }
            if (n.right != null) {
                deque.add(n.right);
                map.put(n.right,floor+1);
            }
        }
        return Math.max(thisNum,maxNum);
    }

	//基于横向遍历
    public static int fun_2(Node root) {
        if (root == null) return 0;
        Node thisLastNode=root;//记录遍历节点层的最后一个节点
        Node nextLastNode=null;//记录遍历节点下一层最后一个结点
        int maxNum=0;
        int thisNum=0;//当前层节点个数
        Deque deque = new ArrayDeque();
        deque.add(root);
        while (!deque.isEmpty()) {
            Node n = deque.poll();
            thisNum++;//删除一个就加1
            if (n.left != null) {
                deque.add(n.left);
                nextLastNode=n.left;//更新最后一个节点
            }
            if (n.right != null) {
                deque.add(n.right);
                nextLastNode=n.right;//更新最后一个节点
            }
            if (n==thisLastNode){//删除的借点和该层节点相同说明该层结束
                thisLastNode=nextLastNode;//将下一层最后的节点给thisLastNode
                nextLastNode=null;//以后动态遍历下一层
                maxNum=Math.max(thisNum,maxNum);//记录最大值
                thisNum=0;
            }
        }
        return maxNum;
    }
}
class Node{
    int value;
    Node left;
    Node right;
    public Node(int num){
        this.value=num;
    }
}

isBST_2递归套路：

class Tree{
    //中序遍历判断
    private static int last=Integer.MIN_VALUE;
    public static boolean isBST_1(Node head){
        if (head==null){
            return true;
        }
        if (!isBST_1(head.left))return false;
        if (last>=head.value)return false;
        else last=head.value;
        return isBST_1(head.right);
    }
    
    
    //套路递归判断
    public static returnType isBST_2(Node head){
        if (head==null)return null;
        returnType leftType= isBST_2(head.left);
        returnType rightType= isBST_2(head.right);

        int min=head.value;//初始值
        int max=head.value;
        boolean flag=true;

        //左判断刷新
        if (leftType!=null){
            if (!leftType.isbst||leftType.max>=head.value)flag=false;
            min=Math.min(leftType.min,head.value);
            max=Math.max(leftType.max,head.value);
        }
        //右判断刷新
        if (rightType!=null){
            if (!rightType.isbst||rightType.min<=head.value)flag=false;
            min=Math.min(rightType.min,head.value);
            max=Math.max(rightType.max,head.value);
        }
        return new returnType(min,max,flag);
    }
    static class returnType{
        boolean isbst;
        int min;
        int max;
        private returnType(int min, int max, boolean flag){
            this.min=min;
            this.max=max;
            this.isbst=flag;
        }
    }
}
class Node{
    int value;
    Node left;
    Node right;
    public Node(int num){
        this.value=num;
    }
}

class Tree {
    public static boolean isCBT(Node head) {
        if (head == null) return true;
        boolean flag = false;
        Deque deque = new ArrayDeque();
        deque.add(head);
        while (!deque.isEmpty()) {
            Node node = deque.pop();
            if ((node.left == null && node.right != null)//左无节点有有节点
                    ||
                    (flag && (node.right != null || node.right != null)))//标记后左右存在节点
                return false;
            if (node.left != null) deque.add(node.left);
            if (node.right != null) deque.add(node.right);
            if (node.left == null || node.right == null) flag = true;//此后不该有子节点，应该放在最后判断，因为判断结果flag不能对此次结果有影响
        }
        return true;
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int num) {
        this.value = num;
    }
}

递归套路：

class Tree {
	//方式一
    public static boolean isF_1(Node head){
        Data data = is_1(head);
        return (1< 
判断是平衡树（套路题） 
递归套路：
 
 
class Tree {
    public static Data isAVL(Node head){
        if (head==null)return new Data(0,true);
        Data lData=isAVL(head.left);
        Data rData=isAVL(head.right);
        int height=Math.max(lData.height,rData.height)+1;
        boolean flag=lData.isAVL&&rData.isAVL&&Math.abs(lData.height-rData.height)<=1;
        return new Data(height,flag);
    }

    static class Data{
        int height;
        boolean isAVL;
        public Data(int height ,boolean is){
            this.height=height;
            this.isAVL=is;
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;
    public Node(int num) {
        this.value = num;
    }
}
 
树结构转成链表（套路题） 
 
class Tree {
    public static Data process(Node x) {
        if (x == null) {
            return new Data(null, null);
        }
        Data leftData = process(x.left);
        Data rightData = process(x.right);
        if (leftData.end != null) {
            leftData.end.right = x;
        }
        x.left = leftData.end;
        if (rightData.start != null) {
            rightData.start.left = x;
        }
        x.right = rightData.start;
        return new Data(leftData.start != null ? leftData.start : x,
                rightData.end != null ? rightData.end : x);
    }

    static class Data {
        Node start;
        Node end;
        public Data(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }
}

class Node {
    int num;
    Node left;
    Node right;
}
 
子搜索二叉树的节点个数（套路题） 
 
节点个数 
class Tree {
    public static int p(Node header) {
        return process(header).num;
    }

    private static Data process(Node x) {
        if (x == null) {
        	//注意min，max初始化值
            return new Data(true, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        Data leftData = process(x.left);
        Data rightData = process(x.right);
        if (rightData.isBST && leftData.isBST && x.value > leftData.max && x.value < rightData.min) {
            return new Data(true, leftData.num + rightData.num + 1,
                    rightData.max == Integer.MIN_VALUE ? x.value : rightData.max,
                    leftData.min == Integer.MAX_VALUE ? x.value : leftData.min);
        } else {
            return new Data(false, Math.max(leftData.num, rightData.num), Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
    }

    private static class Data {
        boolean isBST;
        int num;
        int max;
        int min;
        public Data(boolean isBST, int num, int max, int min) {
            this.isBST = isBST;
            this.num = num;
            this.max = max;
            this.min = min;
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
}
 
返回子最大搜索树的根节点 
class Tree {
    public static Node p(Node header) {
        return process(header).root;
    }

    private static Data process(Node x) {
        if (x == null) {
            return new Data(true, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, null);
        }
        Data leftData = process(x.left);
        Data rightData = process(x.right);
        if (leftData.isBST && rightData.isBST && x.value > leftData.max && x.value < rightData.min) {
            return new Data(true, leftData.num + rightData.num + 1,
                    rightData.max == Integer.MIN_VALUE ? x.value : rightData.max,
                    leftData.min == Integer.MAX_VALUE ? x.value : leftData.min, x);
        } else {
            //一方不是搜索树 或者 双方都不是 或者 双方是但x不满足 就将最大的num向上传递，双方不是之前必定遇见一方是一方不是，那一方不是的将该方最大子搜索树的个数传递上来
            return new Data(false,Math.max(leftData.num,rightData.num),Integer.MIN_VALUE,Integer.MAX_VALUE,leftData.num>rightData.num?leftData.root:rightData.root);
        }
    }

     private static class Data {
        boolean isBST;
        int num,max,min;
        Node root;
        public Data(boolean isBST, int num, int max, int min, Node root) {
            this.isBST = isBST;
            this.num = num;
            this.max = max;
            this.min = min;
            this.root = root;
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
}
 
树节点最远距离（套路题） 

 递归套路：
 
根据子树最大深度计算出经过当前节点的最长距离
向上传递子树和经过当前节点最长距离 的最大值
最长距离需要子树深度
所以递归数据包括最大距离和最大深度
 
class U {
    public static Data maxLength(Node head){
        if (head==null)return new Data(0,0);
        Data ld=maxLength(head.left);
        Data rd=maxLength(head.right);
        int maxLen=Math.max(ld.maxHeight+rd.maxHeight+1,Math.max(ld.maxLen,ld.maxLen));
        int maxHeight=Math.max(ld.maxHeight,rd.maxHeight)+1;
        return new Data(maxLen,maxHeight);
    }
    private static class Data{
        int maxLen;
        int maxHeight;
        private Data(int maxLen,int maxHeight){
            this.maxLen=maxLen;
            this.maxHeight=maxHeight;
        }
    }
}
 
最大快乐值（套路题） 

 递归套路：
 
最大值和每个节点是否去有关，就是取 当前节点不去（0）+子节点去或不去的最大值 和 当前节点去（happy）+子节点不去的最大值
每个节点的去和不去都会直接影响父类节点，间接影响祖宗节点。
只要递归传递该节点去和不去的最大值信息即可。
 
class U {
    public static Data maxHappy(Node head){
        if (head.nexts==null)return new Data(0,head.happy);
        int lai=head.happy;
        int bu=0;
        for (Node node:head.nexts){
            Data data = maxHappy(node);
            lai+=data.maxBu;//该节点去，子节点不能去
            bu+=Math.max(data.maxBu,data.maxLai);//该节点不去，子节点可取可不去
        }
        return new Data(bu,lai);
    }
    private static class Data{
        int maxBu;
        int maxLai;
        private Data(int maxBu,int maxLai){
            this.maxBu =maxBu;
            this.maxLai =maxLai;
        }
    }
}
class Node {
    int happy;
    Node[] nexts;
}
 
树的个数 
 
public class Test {
    public static int pro(int N) {
        if (N == 0 || N == 1) return 1;
        int res = 0;
        for (int i = 0; i < N; i++) {
            int l = pro(i);
            int r = pro(N - i - 1);
            res += l * r;
        }
        return res;
    }
}
 
查找树中两个节点的最近共父类节点 
该路径上不存在寻找的o1或o2，就回馈上一次递归null
路径上存在o1或o2，返回标记告诉上一次递归存在o1或o2
直到在某次递归时判断出左右路径都回馈了有o1或o2，就将该父节点返回
将返回的父节点以返回值的方式传给上一次递归直至结束递归。
 
class Tree {
    
    public static Node ancestor(Node header, Node o1, Node o2) {
        if (header == null || o1 == header || o2 == header) return header;
        Node lNode = ancestor(header.left, o1, o2);
        Node rNode = ancestor(header.right, o1, o2);
        
        //该条件只会成功一次，返回的header就是我们所要找的节点
        // 如何将这个节点返回第一次调用这个函数时？
        //      由于我们不知道这个父节点是它的父节点的左还是右
        //      但是我们知道成功进入该条件后的所有递归中只能出现一边为null，另一边为header节点
        //      所以 返回： lNode != null ? lNode : rNode
        //          另外这句话也会在找到目标节点前将o1或o2传到上一个递归中，代表着这个路径上存在o1或o2
        //          当路径上没有o1或o2时，lNode和rNode均为空，随便返回一个
        if (lNode != null && rNode != null)
            return header;
        return lNode != null ? lNode : rNode;
    }
}
class Node {
    int value;
    Node left;
    Node right;
    public Node(int num) {
        this.value = num;
    }
}
 
查找后继结点 
有右节点，右树上的最左节点
无右节点，递归寻找节点是父节点左节点的点
否则空
 
class Tree {
    public static Node process(Node node){
        if (node==null)return null;
        if (node.right!=null)return leftLast(node.right);//有右节点
        Node parentTail=node.parent;
        while (parentTail!=null&&parentTail.left!=node){//递归寻找节点
            node=parentTail;
            parentTail=parentTail.parent;
        }
        return parentTail;
    }
    private static Node leftLast(Node head){//一直寻找左节点
        while (head.left!=null)
            head=head.left;
        return head;
    }
}

class Node {
    int value;
    Node left;
    Node right;
    Node parent;
    public Node(int num) {
        this.value = num;
    }
}
 
折纸凹凸问题 

 上次每个折痕都有两个子折痕，上凹下凸，也就是二叉树节点都有一个凹左节点一个凸右节点。这些折痕的顺序就是二叉树的中序遍历。
 
class Tree {
    
    public static void pre(int N){
        pre(N,true);
    }
    private static void pre(int num,boolean down){
        if (num==0)return;
        pre(num-1,true);//true表示凹，false表示凸
        System.out.print(down?"down ":"up ");
        pre(num-1,false);
    }
}
 
前中序推后序遍历 
 
public class Test {
    public static void main(String[] args) {
        int[] post = genPost(new int[]{1, 2, 4, 5, 3, 6, 7}, new int[]{4, 2, 5, 1, 6, 3, 7});
        System.out.println(Arrays.toString(post));
    }

    public static int[] genPost(int[] pre, int[] in) {
        int[] post = new int[pre.length];
        HashMap map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        genPost(pre, 0, pre.length - 1, in, 0, in.length - 1, post, 0, post.length - 1, map);
        return post;
    }

    private static void genPost(int[] pre, int preStart, int preEnd,
                                int[] in, int medStart, int medEnd,
                                int[] post, int postStart, int postEnd,
                                HashMap map) {
        if (preStart > preEnd) {
            return;
        }
        if (postStart == postEnd) {
            post[postStart] = pre[preStart];
            return;
        }
        //每一轮的前序第一个元素就是后序最后一个元素，在后续的genPost中不能再包含其他元素
        post[postEnd] = pre[preStart];

        //此时寻找pre[preStart]在med中的索引indexStart，那么最后的 indexStart - medStart 就是中间元素个数
        int indexStart = map.get(pre[preStart]);
        
        //以pre中preStart位置的元素为左右分割点,根据 indexStart 确定pre,in,post中的数据范围
        genPost(pre, preStart + 1, preStart + indexStart - medStart,
                in, medStart, indexStart - 1,
                post, postStart, postStart + indexStart - medStart - 1,
                map);
        genPost(pre, preStart + indexStart - medStart + 1, preEnd,
                in, indexStart + 1, medEnd,
                post, postStart + indexStart - medStart, postEnd - 1,
                map);
    }
}
 
哈夫曼最小代价问题 
 
class Tree {
    public static int lessConsumer(int[] arr){
        if (arr.length==1)return arr[0];
        PriorityQueue queue = new PriorityQueue<>();//内部元素为堆结构（优先队列）
        for (int i : arr)
            queue.add(i);
        int sum=0;
        while (queue.size()>1){
            //构建赫夫曼树
            int num1=queue.poll();
            int num2=queue.poll();
            sum+=(num1+num2);
            queue.add(num1+num2);
        }
        return sum;
    }
}