[数据结构与算法]W6_二叉树

144. 二叉树的前序遍历

难度 1

题解 1 递归

var preorderTraversal = function(root) {
    let res = [];
    let dfs = (root) => {
        if(root == null) return;
        res.push(root.val);
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return res;
};

复杂度

思路

102. 二叉树的层序遍历

难度 2

题解 1 迭代

var levelOrder = function(root) {
    let res = [], queue = [];
    queue.push(root);
    if(!root) return res;
    while(queue.length){
        let len = queue.length;
        let curLevel = [];
        for(let i = 0; i< len;i++){
            let node = queue.shift();
            curLevel.push(node.val);
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        res.push(curLevel);
    }
    return res;
};

复杂度

思路

226. 翻转二叉树

难度 2

题解 1 迭代

var invertTree = function(root) {
    const change = (root,left,right)=>{
        let temp = left;
        left = right;
        right = temp;
        root.left = left;
        root.right = right;
    }
    let queue = [];
    if(!root) return root;
    queue.push(root);
    while(queue.length){
        let len = queue.length;
        while(len--){
            let node = queue.shift();
            change(node, node.left, node.right);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return root;
};

复杂度

思路

101. 对称二叉树

难度 1

题解

var isSymmetric = function(root) {
    if(!root) return root;
    let queue = [];
    queue.push(root.left);
    queue.push(root.right);
    while(queue.length){
        let leftNode = queue.shift();
        let rightNode = queue.shift();
        if(leftNode == null && rightNode == null) continue;
        if(leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;
        queue.push(leftNode.left);
        queue.push(rightNode.right);
        queue.push(leftNode.right);
        queue.push(rightNode.left);
    }
    return true;
};

复杂度

思路

不难, 和层序遍历的思路一致, 不过要考虑的是变通

就是如何把左子树右子树安排进去, 用 if 判断 null 的情况

104. 二叉树的最大深度

难度 1

题解 1 层级遍历

var maxDepth = function(root) {
    let count = 0, queue = [];
    if(!root) return 0;
    queue.push(root);
    while(queue.length){
        let len = queue.length;
        count++;
        while(len--){
            let node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }

    }
    return count;
};

复杂度

题解 2 递归

var maxDepth = function(root) {
    if(!root) return 0;
    return 1+ Math.max(maxDepth(root.left),maxDepth(root.right));
};

复杂度

思路

如果用 res[]存curLevel会出现错误, 要找到原因

111. 二叉树的最小深度

难度 1

题解 1 递归

var minDepth = function(root) {
    if(!root) return 0;
    if(!root.left&&!root.right) return 1;
    if(!root.left) return 1+minDepth(root.right);
    if(!root.right) return 1+minDepth(root.left);
    return 1+ Math.min(minDepth(root.left),minDepth(root.right));
};

复杂度

题解 2 迭代

var minDepth = function(root) {
    if(!root) return 0;
    let queue = [root], count = 0;
    while(queue.length){
        let len = queue.length;
        count++;
        while(len--){
            let node = queue.shift();
            if(!node.left&&!node.right) return count;
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return count;
};

复杂度

思路

递归时注意限制条件, 如果没有第一个左右子节点但有另外一个, 按另外一个的来

222. 完全二叉树的节点个数

难度 1

题解 1 迭代

var countNodes = function(root) {
    if(!root) return 0;
    let queue = [root],count = 0;
    while(queue.length){
        let len = queue.length;
        while(len--){
            let node = queue.shift();
            count++;
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return count;
};

复杂度

时间 On 空间 On

题解 2 递归

var countNodes = function(root) {
    let getNumbers = (root) =>{
        if(!root) return 0;
        let getLeft = getNumbers(root.left);
        let getRight = getNumbers(root.right);
        return getLeft + getRight + 1;
    }
    return getNumbers(root);
};

复杂度

时间 On 空间 Ologn

思路

110. 平衡二叉树

难度 2

题解 1 递归

var isBalanced = function(root) {
    const getHeight = (root) => {
        if(!root) return 0;
        let leftHeight = getHeight(root.left);
        if(leftHeight === -1) return -1;
        let rightHeight = getHeight(root.right);
        if(rightHeight === -1) return -1;
        if(Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }else{
            return 1+ Math.max(leftHeight, rightHeight);
        }
    }
    return !(getHeight(root) === -1);
};

复杂度

思路

这一题迭代很难做, 迭代要用后序处理

257. 二叉树的所有路径

难度 2

题解 1 递归

var binaryTreePaths = function(root) {
    let res = [];
    const path = (node,curPath) => {
        if(!node.left&&!node.right){
            curPath+=node.val;
            res.push(curPath);
            return;
        } 
        curPath+= node.val + '->';
        node.left && path(node.left,curPath);
        node.right && path(node.right,curPath);
    }
    path(root, '');
    return res;
};

复杂度

思路

404. 左叶子之和

难度 2

题解 1 递归

var sumOfLeftLeaves = function(root) {
    const countLeft = (node) =>{
        if(!node) return 0;
        let leftValue = countLeft(node.left);
        let rightValue = countLeft(node.right);
        let leftOnlyValue = 0;
        if(node.left&&!node.left.left&&!node.left.right){
            leftOnlyValue = node.left.val;
        }
        let sum = leftValue + leftOnlyValue + rightValue;
        return sum;
    }
    return countLeft(root);
};

复杂度

思路

513. 找树左下角的值

难度 2

题解 1 迭代

var findBottomLeftValue = function(root) {
    let res, queue = [root];
    while(queue.length){
        let len = queue.length;
        while(len--){
            let node = queue.shift();
            if(len>0) res = node.val;
            node.left&& queue.push(node.left);
            node.right&& queue.push(node.right);
        }
    }
    return res;
};

复杂度

思路

这一题迭代比递归好用, 当 i==0 时就是最后一层, 这里注意 while len-- 时会出错

112. 路径总和

难度 3

题解 1 递归

var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    const getSum = (node, end) => {
        if(end === 0&&!node.left&&!node.right) return true;
        if(!node.left&&!node.right) return false;
        if(node.left &&getSum(node.left,end-node.left.val)) return true;
        if(node.right &&getSum(node.right,end-node.right.val)) return true;
        return false;
    }
    return getSum(root,targetSum-root.val);
};

复杂度

思路

很有意思, 减到 0 且到叶节点则停止

106. 从中序与后序遍历序列构造二叉树

难度

题解

var buildTree = function(inorder, postorder) {
    if(!inorder.length) return null;
    let rootVal = postorder.pop();
    let rootIndex = inorder.indexOf(rootVal);
    const root = new TreeNode(rootVal);
    root.left = buildTree(inorder.slice(0,rootIndex),postorder.slice(0,rootIndex));
    root.right = buildTree(inorder.slice(rootIndex+1),postorder.slice(rootIndex));
    return root;
};

复杂度

思路

前序和中序也可以构成二叉树, 这里的重点是 rootindex 的位置

前序和后序则不行, 因为没有中序表明 root 的位置

654. 最大二叉树

难度 4

题解 1 递归

var constructMaximumBinaryTree = function(nums) {
    const buildTree = (nums, left, right) =>{
        if(left>right) return null;
        let maxVal =-1, maxIndex=-1;
        for(let i = left;i<=right;i++){
            if(nums[i]>maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        let root = new TreeNode(maxVal);
        root.left = buildTree(nums,left, maxIndex-1);
        root.right = buildTree(nums, maxIndex+1, right);
        return root;
    }
    return buildTree(nums, 0, nums.length-1);
};

复杂度

思路

条件和 return 不好想

617. 合并二叉树

难度 2

题解 1 递归

var mergeTrees = function(root1, root2) {
    const preOrder = (node1, node2) => {
        if(!node1) return node2;
        if(!node2) return node1;
        node1.val += node2.val;
        node1.left = preOrder(node1.left, node2.left);
        node1.right = preOrder(node1.right,node2.right);
        return node1;
    }
    return preOrder(root1,root2);
};

复杂度

思路

700. 二叉搜索树中的搜索

难度 1

题解 1 递归

var searchBST = function(root, val) {
    if(!root||root.val==val) return root;
    if(root.val>val){
        return searchBST(root.left, val);
    }
    if(root.val<val){
        return searchBST(root.right, val);
    }
};

复杂度

题解 2 迭代

var searchBST = function (root, val) {
    while (root !== null) {
        if (root.val > val)
            root = root.left;
        else if (root.val < val)
            root = root.right;
        else 
            return root;
    }
    return null;
};

复杂度

思路

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

98. 验证二叉搜索树

难度 2

题解 1 递归

var isValidBST = function(root) {
    let arr = [];
    const inOrder = (root) => {
        if(root){
            inOrder(root.left);
            arr.push(root.val);
            inOrder(root.right);
        }
    }
    inOrder(root);
    for(let i = 0;i<arr.length-1;i++){
        if(arr[i]>=arr[i+1]) return false;
    }
    return true;
};

复杂度

思路

二叉搜索树特性, 中序排列是升序

530. 二叉搜索树的最小绝对差

难度 1

题解 1 递归

var getMinimumDifference = function(root) {
    let arr = [];
    const inOrder = (root) => {
        if(root){
            inOrder(root.left);
            arr.push(root.val);
            inOrder(root.right);
        }
    }
    inOrder(root);
    let minNum = 0, minRes = Number.MAX_SAFE_INTEGER;
    for(let i = 0;i<arr.length-1;i++){
        minNum = arr[i+1]-arr[i];
        minRes = minRes<minNum ? minRes:minNum;
    }
    return minRes;
};

复杂度

思路

这里 minRes 用最大安全数, 也可以直接在 for 循环中 minRes 和 minNum 对比

501. 二叉搜索树中的众数

难度 2

题解 1 递归+map

var findMode = function(root) {
    let map = new Map();
    const inOrder = (root) => {
        if(root){
            inOrder(root.left);
            map.set(root.val, map.has(root.val)?map.get(root.val)+1:1);
            inOrder(root.right);
        }
    }
    inOrder(root);
    let maxCount = map.get(root.val);
    let res = [];
    for( let [key,value] of map){
        if(value == maxCount){
            res.push(key);
        }
        if(value>maxCount){
            res = [];
            maxCount = value;
            res.push(key);
        }
    }
    return res;
};

复杂度

思路

return 的是数组

res 要重新赋值为 []

这个 for of 很巧妙

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

难度 3

题解 1 回溯

var lowestCommonAncestor = function(root, p, q) {
    const travelTree = (root, p, q) => {
        if(!root||root==p||root==q){
            return root;
        }
        let left = travelTree(root.left,p,q);
        let right = travelTree(root.right,p,q);
        if(left&&right) return root;
        if(!left) return right;//说明左边不是答案
        return left;
    }
    return travelTree(root,p,q);
};

复杂度

思路

这题对递归和回溯有很高要求

要明白 let left 是对整个树进行搜索, 如果只是 if 就只是对那条边进行搜索

需要明白一层一层返回是如何做到的

最后的答案是返回到树的头结点再返回答案的

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

难度

题解 1 普通树递归

var lowestCommonAncestor = function(root, p, q) {
    const travelTree = (root, p, q) => {
        if(!root||root==p||root==q){
            return root;
        }
        let left = travelTree(root.left,p,q);
        let right = travelTree(root.right,p,q);
        if(left&&right) return root;
        if(!left) return right;//说明左边不是答案
        return left;
    }
    return travelTree(root,p,q);
};

复杂度

题解 2 搜索树递归

var lowestCommonAncestor = function(root, p, q) {
    if(!root) return root;
    if(root.val>p.val&&root.val>q.val){
       let left = lowestCommonAncestor(root.left,p,q);
       return left!==null && left;
    }
    if(root.val<p.val&&root.val<q.val){
        let right = lowestCommonAncestor(root.right,p,q);
        return right!==null && right;
    }
    return root;
};

复杂度

思路

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

难度

题解 1 递归

var insertIntoBST = function(root, val) {
    const inOrder = (root,val) =>{
        if(!root){
            let node = new TreeNode(val);
            return node;
        }
        if(root.val>val){
            root.left = inOrder(root.left,val);
        }
        if(root.val<val){
            root.right = inOrder(root.right,val);
        }
        return root;
    }
    return inOrder(root,val);
};

复杂度

思路

不是很明白

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

难度 5

题解 1 递归

var deleteNode = function (root, key) {
    if (root === null)
        return root;
    if (root.val === key) {
        if (!root.left)
            return root.right;
        else if (!root.right)
            return root.left;
        else {
            let cur = root.right;
            while (cur.left) {
                cur = cur.left;
            }
            cur.left = root.left;
            root = root.right;
            delete root;
            return root;
        }
    }
    if (root.val > key)
        root.left = deleteNode(root.left, key);
    if (root.val < key)
        root.right = deleteNode(root.right, key);
    return root;
};

复杂度

思路

巨难

669. 修剪二叉搜索树

难度 2

题解 1 递归

var trimBST = function(root, low, high) {
    if(!root) return root;
    if(root.val<low){
        let right = trimBST(root.right, low, high);
        return right;
    }
    if(root.val>high){
        let left = trimBST(root.left, low,high);
        return left;
    }
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
};

复杂度

思路

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

难度 3

题解 1

var sortedArrayToBST = function (nums) {
    const buildTree = (Arr, left, right) => {
        if (left > right)
            return null;
        let mid = Math.floor(left + (right - left) / 2);

        let root = new TreeNode(Arr[mid]);
        root.left = buildTree(Arr, left, mid - 1);
        root.right = buildTree(Arr, mid + 1, right);
        return root;
    }
    return buildTree(nums, 0, nums.length - 1);
};

复杂度

思路

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

难度 2

题解 1 递归

var convertBST = function(root) {
    let pre = 0;
    const reverseOrder = (root) =>{
        if(root){
            reverseOrder(root.right);
            root.val += pre;
            pre = root.val;
            reverseOrder(root.left);
        }
    }
    reverseOrder(root);
    return root;
};

复杂度

思路

逆序相加