二叉树变异之noneTree、circleTree

判断一棵二叉树是noneTree，还是circleTree

noneTree：一个节点有多个父节点

circleTree：节点之间形成一个单向的环

//**java**
//节点对象
class Node {
    private Node left; //左子节点
    private Node right;//右子节点
    private String value;//值
    private int flag;    //访问次数
    private Stack<Node> pstack = new Stack<>(); //上级节点栈

    public Node(String value, int flag) {
        this.value = value;
        this.flag = flag;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public int getFlag() {
        return flag;
    }

    public void setFlag(int flag) {
        this.flag = flag;
    }


    public Stack<Node> getPstack() {
        return pstack;
    }

    public void setPstack(Stack<Node> pstack) {
        this.pstack = pstack;
    }
}

public class TreeSearch {

    /**
     * noneTree 不止一个父节点
     * circle 节点之间形成一个闭环，必然是noneTree
     */

    //当定义circle为单边时，如root-->left---->root
    static boolean isSingleSide = false;
    //存储上级节点
    static Stack<Node> stack = new Stack<>();
    //是否为circle
    static boolean ic = false;


    public static void main(String[] args) {

        Node n = new Node("root", 1);
        Node nl = new Node("nl", 1);
        Node nr = new Node("nr", 1);
        Node nrr = new Node("nrr", 1);
        Node nrl = new Node("nrl", 1);
        Node nrlr = new Node("nrlr", 1);
        Node nll = new Node("nll", 1);
        Node nlr = new Node("nlr", 1);
        Node nlll = new Node("nlll", 1);
        Node nllll = new Node("nllll", 1);
        Node nlllll = new Node("nlllll", 1);


        //right
        n.setRight(nr);
        nr.setLeft(nrl);
        nr.setRight(nrr);
        nrl.setLeft(nll);
        nrr.setRight(n);


        //left
//        n.setLeft(nl);
//        n.setRight(nr);
//        nl.setLeft(nll);
//        nll.setLeft(nlll);
//        nll.setLeft(n);


        isSingleSide = true;
        preOrder(n);
        if (!ic)//如果左单边没找到则再找右单边
            postOrder(n);
        System.out.println(ic);


    }

    /**
     * 前序遍历，寻找左单边
     *
     * @param n
     */
    public static void preOrder(Node n) {


        String value = n.getValue();
        // System.out.println(value + "  -  " + n.getPstack().size());


        if (ic || n.getFlag() >= 2) {
            return;
        }
        n.setFlag(n.getFlag() + 1);
        Node left = n.getLeft();
        stack.push(n);

        if (left != null) {
            if (n.getPstack().contains(left)) {
                ic = true;
                return;
            }
            left.setPstack(stack);
            preOrder(left);
        }

        Node right = n.getRight();
        if (right != null) {
            if (n.getPstack().contains(right)) {
                ic = true;
                return;
            }
            right.setPstack(stack);
            preOrder(right);
        }


        if (isSingleSide) { // 形成circle的节点都是左子节点，root除外
            stack.clear();
        } else {    //形成circle的是不必是同种节点
            stack.pop();  //当前节点退栈
        }

    }


    /**
     * 后序遍历，寻找右单边
     *
     * @param n
     */
    public static void postOrder(Node n) {


        //防止stack overflow
        if (n.getFlag() >= 2) {
            return;
        }
        n.setFlag(n.getFlag() + 1);
        stack.push(n);

        Node right = n.getRight();
        if (right != null) {
            if (n.getPstack().contains(right)) {
                ic = true;
                return;
            }
            right.setPstack(stack);
            postOrder(right);
        }

        Node left = n.getLeft();


        if (left != null) {
            if (n.getPstack().contains(left)) {
                ic = true;
                return;
            }
            left.setPstack(stack);
            postOrder(left);
        }

        if (isSingleSide) {
            stack.clear();
        } else
            stack.pop();

    }

}