二叉树

class TreeNode {
    constructor(val) {
        this.value = val;
        this.left = null;
        this.right = null;
    }
}
// 二叉搜索树插入值
function insertIntoBST(root, val) {
    if (root == NULL) {
        let node = new TreeNode(val);
        return node;
    }
    if (root.val > val) root.left = insertIntoBST(root.left, val);
    if (root.val < val) root.right = insertIntoBST(root.right, val);
    return root;
}
// 记录父节点
function solution(root, val) {
    let parent;
    function traversal(cur, val) {
        if (cur === null) {
            let node = new TreeNode(val);
            if (parent.val > val) {
                parent.left = node;
            } else {
                parent.right = node;
            }
            return;
        }
        parent = cur;
        if (cur.val > val) traversal(cur.left, val);
        if (cur.val < val) traversal(cur.right, val);
        return;
    }
    function insertIntoBST(root, val) {
        parent = new TreeNode(0);
        if (root == NULL) {
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }
    insertIntoBST(root, val)
}
// 迭代法
function insertIntoBST(root, val) {
    if (root == NULL) {
        let node = new TreeNode(val);
        return node;
    }
    let cur = root;
    let parent = root;
    while (cur != NULL) {
        parent = cur;
        if (cur.val > val) cur = cur.left;
        else cur = cur.right;
    }
    node = new TreeNode(val);
    if (val < parent.val) parent.left = node;
    else parent.right = node;
    return root;
}
// 修剪✂️二叉搜索树
function trimBST(root, low, high) {
    if (root == null) return null;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}
// 迭代法修剪✂️二叉搜索树
function trimBST(root, low, high) {
    if (!root) return null;
    while (root.value < low || root.value > high) {
        if (root.value < low) {
            root = root.right
        } else {
            root = root.left
        }
    }
    let cur = root;
    while (cur.left.value < low) {
        cur.left = cur.left.right;
    }
    cur = root;
    while (cur.right.value > high) {
        cur.right = cur.right.left;
    }
    return root;
}
// 把搜索树转换为累加树
function traversal(cur) { // 右中左遍历
    if (cur == NULL) return;
    traversal(cur.right);
    cur.val += pre;
    pre = cur.val;
    traversal(cur.left);
}
function convertBST(root) {
    pre = 0;
    traversal(root);
    return root;
}

后序遍历

前序遍历

中序遍历

迭代法中序遍历

function Node(val) {
    this.left = null;
    this.right = null;
    this.val = val;
}
const inorderTraversal = (root) => {
    let result = [];
    let st = [];
    if (root !== null) st.push(root);
    while (st.length > 0) {
        let node = st[st.length - 1];
        if (node !== null) {
            st.pop();
            if (node.right) st.push(node.right);
            st.push(node);
            st.push(null);
            if (node.left) st.push(node.left);
        } else {
            st.pop();
            node = st[st.length - 1];
            result.push(node.val)
        }
    }
    return result;
}