morris

function Node(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
let node5 = new Node(5);
let node6 = new Node(6);
let node7 = new Node(7);

node4.left = node2;
node4.right = node5;
node2.left = node1
node2.right = node3;
node5.right = node7;


// node1.left = node2;
// node1.right = node3;
// node2.left = node4;
// node2.right = node5;
// node3.left = node6;
// node4.left = node7
//
//
// function morris(root) {
//     let cur = root;
//     let maxRight = null;
//     while (cur) {
//         // console.log(cur.val);
//         maxRight = cur.left;
//         if (maxRight) { // 有左树
//             while (maxRight.right && maxRight.right !== cur) maxRight = maxRight.right;
//             if (!maxRight.right) {
//                 console.log(cur.val);
//                 maxRight.right = cur;
//                 cur = cur.left;
//                 // continue;
//             } else if (maxRight.right === cur) {
//                 maxRight.right = null;
//                 cur = cur.right;
//             }
//         } else {
//             console.log(cur.val);
//             cur = cur.right;// 无左树
//         }
//     }
// }
//
// morris(node1);

// function Node(val){
//     this.val = val;
//     this.next = null;
// }
// let node1 = new Node(1);
// let node2 = new Node(2);
// let node3 = new Node(3);
// let node4 = new Node(4);
// let node5 = new Node(5);
//
// node1.next = node2;
// node2.next = node3;
// node3.next = node4;
// node4.next = node5;
//
// function reverseRootList(root){
//     let cur = root;
//     let prev = null;
//     let next = cur.next;
//     while (cur){
//         next = cur.next;
//         cur.next = prev;
//         prev = cur;
//         cur = next;
//     }
//     return prev
// }
// const res = reverseRootList(node1)
// console.log(res);

// morris思路
// 1. 没有左子树：cur = cur.right
// 2. 有左子树，找到左子树的最右节点mostRight
//    - 如果 mostRight.right = null，则 mostRight.right = cur
//    - 如果 mostRight.right = cur，则 mostRight.right = null，cur = cur.right
// function morris(root) {
//     let cur = root;
//     let mostRight;
//     while (cur) {
//         if (cur.left) { // 有左子树
//             mostRight = cur.left;
//             while (mostRight.right && mostRight.right !== cur) mostRight = mostRight.right;
//             if (!mostRight.right) {
//                 mostRight.right = cur;
//                 cur = cur.left;
//             } else if (mostRight.right === cur) {
//                 // 有左子树的节点会进入这里
//                 const lastNode = reverseRootList(cur.left);
//                 // console.log(lastNode);
//                 // printNode(lastNode)
//                 mostRight.right = null;
//                 cur = cur.right;
//             }
//         } else {
//             // console.log(cur.val);
//             cur = cur.right;
//         }
//     }
// }
//
// morris(node1);
//
// function reverseRootList(root) {
//     let prev = null;
//     let cur = root;
//     let right = root.right;
//     while (cur) {
//         cur.right = prev;
//         prev = cur;
//         cur = right;
//         if (cur) right = cur.right;
//     }
//     return prev;
// }
//
// function printNode(root) {
//     while (root) {
//         console.log(root.val);
//         root = root.right;
//     }
// }

// var searchBST = function (root, val) {
//     if(root === null) return;
//     if(root.val === val) return root;
//     const leftRes = searchBST(root.left,val);
//     const rightRes = searchBST(root.right,val);
//     return leftRes || rightRes;
// };
// const ans = searchBST(node1, 2)
// console.log(ans);

/* 判断是否是搜索二叉树 */
function morris(root) {
    let cur = root;
    let mostRight;
    let curH = 0;
    let minH = Infinity;
    let prev;
    while (cur) {
        if (cur.left) { // 有左子树时
            let mostH = 1;
            mostRight = cur.left;
            while (mostRight.right && mostRight.right !== cur) {
                mostH++;
                mostRight = mostRight.right;
            }
            if (mostRight.right === cur) {
                curH -= mostH;
                if (prev !== undefined && prev.left === null) {
                    console.log('上一个节点的值：', prev.val, '上一个左子树的深度：', mostH, '当前节点的值：', cur.val, '当前节点的深度：', curH);
                    minH = Math.min(minH, curH + mostH)
                }
                mostRight.right = null;
                prev = cur;
                cur = cur.right;
            } else {
                curH++;
                prev = cur;
                mostRight.right = cur;
                cur = cur.left
            }
        } else {
            prev = cur;
            curH++;
            cur = cur.right;
        }
    }
    let lastNodeListH = 1;
    let node = root;
    while (node.right) {
        lastNodeListH++;
        node = node.right
    }
    if (node.left === null && node.right === null) minH = Math.min(minH, lastNodeListH);
    return minH
}

const res = morris(node4)
console.log(res);