leetcode每天5题-Day43（二叉树8）

1. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先-中等
讲解

思路：遍历顺序很重要，因为要把左子树和右子树的结果返回给根节点，所以要自底向上遍历，只能采用后序遍历（即回溯）。

var lowestCommonAncestor = function(root, p, q) {
    // 1. 确定递归的函数
    const travelTree = function(root,p,q) {
        // 2. 确定递归终止条件
        if(root === null || root === p||root === q) {
            return root;
        }
        // 3. 确定递归单层逻辑
        let left = travelTree(root.left,p,q);
        let right = travelTree(root.right,p,q);
        if(left !== null&&right !== null) {
            return root;
        }
        if(left ===null) {
            return right;
        }
        return left;
    }
   return  travelTree(root,p,q);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先-中等
视频讲解

思路：利用二叉搜索树的性质，当当前节点小于p和q的值时，就递归去遍历右子树；当当前节点大于p和q的值时，就递归去遍历左子树；遇到的第一个值介于p和q之间的节点，就是最近公共祖先。

递归

var lowestCommonAncestor = function(root, p, q) {
    // 1. 使用给定的递归函数lowestCommonAncestor
    // 2. 确定递归终止条件
    if(root === null) return root;
    if(root.val > p.val && root.val > q.val) {
        // 向左子树查询
         return lowestCommonAncestor(root.left, p, q);
    }
    if(root.val < p.val && root.val < q.val) {
        // 向右子树查询
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

迭代

var lowestCommonAncestor = function(root, p, q) {
    while(root) {
        if(root.val > p.val && root.val>q.val) {
            root = root.left;
        }else if(root.val < p.val && root.val < q.val) {
            root = root.right;
        }else {
            return root;
        }
        
    }
    return null;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

很妙的一种解法

思路：利用root和p与root和q的差值来判断p与q是否在同一侧

var lowestCommonAncestor = function(root, p, q) {
    // q p 在同一侧
    while((root.val-p.val) * (root.val-q.val)>0){
        root = p.val > root.val ? root.right : root.left;
    }
    return root;
};
1
2
3
4
5
6
7

3. 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作-中等
讲解

思路：最直观也最简单的做法是不改变二叉搜索树原本的结构，把新节点插入到叶子节点位置。

自己的解法

思路：递归。刚开始是在原函数，也就是给定函数的基础上递归的，在递归函数内部用了if(!root) return null;，当第一次提交时，判空的时候出现了问题，也就是当给定一个空树时，函数就直接返回null了。所以我后面先对给定的是否是一棵空树这种特殊情况做下判断，再进行递归。

看了代码随想录的视频讲解与代码，才知道我这种解法没有完成新加入节点和其父节点的赋值操作。

var insertIntoBST = function(root, val) {
    let newNode = new TreeNode(val);
    if(!root) return newNode;
    const insert = (root, val) => {
        if(!root) return null;
        if(root.val < val) {
            let l = insert(root.right, val);
            if(!l) root.right = newNode;
        } else if(root.val > val) {
            let r = insert(root.left, val);
            if(!r) root.left = newNode;
        }
        return root;
    }
    return insert(root, val);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结：通过递归函数返回值完成新加入节点的父子关系赋值操作，下一层将加入节点返回，本层用root.left或者root.right将其接住。

有返回值的递归

var insertIntoBST = function(root, val) {
        if (root === null) {
            let node = new TreeNode(val);
            return node;
        }
        if (root.val > val)
            root.left = insertIntoBST(root.left, val);
        else if (root.val < val)
            root.right = insertIntoBST(root.right, val);
        return root;
};
1
2
3
4
5
6
7
8
9
10
11

无返回值的递归

这种解法看着有点绕，我本来以为是改变了二叉树的结构，但其实并没有。新建一个节点parent，解决不知新节点应该是左叶子节点还是右叶子节点的问题

var insertIntoBST = function (root, val) {
    let parent = new TreeNode(0);
    const preOrder = (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)
            preOrder(cur.left, val);
        if (cur.val < val)
            preOrder(cur.right, val);
    }
    if (root === null)
        root = new TreeNode(val);
    preOrder(root, val);
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

迭代

var insertIntoBST = function (root, val) {
    if (root === null) {
        root = new TreeNode(val);
    } else {
        let parent = new TreeNode(0);
        let cur = root;
        while (cur) {
            parent = cur;
            if (cur.val > val)
                cur = cur.left;
            else
                cur = cur.right;
        }
        let node = new TreeNode(val);
        if (parent.val > val)
            parent.left = node;
        else
            parent.right = node;
    }
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4. ⭐删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点-中等
讲解

这道题相比于上一题插入节点要难得多，因为插入节点不用改变二叉搜索树的结构，但本题有可能要重构二叉搜索树。

删除二叉搜索树中的节点有以下几种情况：

1. 未找到需要删除的节点；
2. 需要删除的节点是叶子节点（左子树和右子树都为空）
3. 需要删除的节点左子树为空，右子树不为空
4. 需要删除的节点左子树不为空，右子树为空
5. 需要删除的节点左子树和右子树都不为空

解题重点：

1. 删除节点的逻辑在终止条件里面
2. 调整二叉树结构时的思路及其调整节点的指针指向
3. 删除节点是通过递归返回值来操作的

递归

var deleteNode = function(root, key) {
    if(!root) return root;
    if(root.val > key) 
        root.left = deleteNode(root.left, key);
    else if(root.val < key) 
        root.right = deleteNode(root.right, key);
    else {
        if(!root.left && !root.right) {
            return null;
        }else if(root.left && !root.right) {
            return root.left;
        }else if(!root.left && root.right) {
            return root.right;
        }else{
            // 当被删除节点左右子树都非空时，利用新建节点cur 找到被删节点右子树的最左侧节点（cur.left），然后把被删节点的左子树放在该节点(cur.left)左子树的位置
            let cur = root.right;
            while(cur.left) cur = cur.left;
            cur.left = root.left;
            return root.right;
        }
    }
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

迭代

var deleteNode = function (root, key) {
    const deleteOneNode = target => {
        if (!target) return target
        if (!target.right) return target.left
        let cur = target.right
        while (cur.left) {
            cur = cur.left
        }
        cur.left = target.left
        return target.right
    }

    if (!root) return root
    let cur = root
    let pre = null
    while (cur) {
        if (cur.val === key) break
        pre = cur
        cur.val > key ? cur = cur.left : cur = cur.right
    }
    if (!pre) {
        return deleteOneNode(cur)
    }
    if (pre.left && pre.left.val === key) {
        pre.left = deleteOneNode(cur)
    }
    if (pre.right && pre.right.val === key) {
        pre.right = deleteOneNode(cur)
    }
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

思考题：普通二叉树删除节点的方式

5. 修剪二叉搜索树

669. 修剪二叉搜索树-中等
讲解

递归

var trimBST = function(root, low, high) {
    if(!root) return root;
    
    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;
};
1
2
3
4
5
6
7
8
9
10

6. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树-简单
讲解

重点：找分割点，分割点是数组中间的元素。

递归

var sortedArrayToBST = function(nums) {
    let len = nums.length;
    if(len < 1) return null;
    // let l = 0; r = len - 1;
    let mid = Math.floor(len / 2);
    let root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));
    return root;
};
1
2
3
4
5
6
7
8
9
10

7. 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树-中等
讲解

这道题刚开始比较难理解，但如果把二叉搜索树转换成一个有序数组，就很好做了，利用双指针从后向前更新元素的值。本题也可以采用双指针方法，重要的是遍历方式，需要按照 右中左 这个顺序去转换。

递归

var convertBST = function(root) {
    let pre = 0;
    const convertInorder = (cur) => {
    	// 递归终止条件
        if(!cur) return;
        // 右
        convertInorder(cur.right);
        // 中
        cur.val += pre;
        pre = cur.val;
        // 左
        convertInorder(cur.left);
    }
    convertInorder(root);
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

迭代

var convertBST = function(root) {
    let pre = 0;
    let stack = [];
    let cur = root;
    while(cur || stack.length) {
        while(cur) {
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        cur.val += pre;
        pre = cur.val;
        cur = cur.left;
    }
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16