数据结构 - [数据结构]二叉树 - 《数据结构与算法》

练习1：递归
练习：复杂递归
- 236. 二叉树的最近公共祖先（剑指 Offer 68 - II. 二叉树的最近公共祖先）">236. 二叉树的最近公共祖先（剑指 Offer 68 - II. 二叉树的最近公共祖先）
练习2: 遍历树与生成树
- 102. 二叉树的层序遍历">102. 二叉树的层序遍历
- 637. 二叉树的层平均值">637. 二叉树的层平均值
- 654. 最大二叉树（数组构建的最大二叉树）">654. 最大二叉树（数组构建的最大二叉树）
- 1~~05. 从前序与中序遍历序列构造二叉树~~/~~106. 从中序与后序遍历序列构造二叉树~~~~ (同105)~~">1~~05. 从前序与中序遍历序列构造二叉树~~/~~106. 从中序与后序遍历序列构造二叉树~~~~ (同105)~~
- 114. 二叉树展开为链表">（先序遍历）114. 二叉树展开为链表
练习3:
- 剑指 Offer 55 - II. 平衡二叉树(110. 平衡二叉树)">剑指 Offer 55 - II. 平衡二叉树(110. 平衡二叉树)
- 剑指 Offer 26. 树的子结构">剑指 Offer 26. 树的子结构
练习：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

练习1：递归

104. 二叉树的最大深度

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

100.相同的树(对比树)

var isSameTree = function(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    if (p.val!==q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

101. 对称二叉树（剑指 Offer 28. 对称的二叉树）

var isSymmetric = function(root) {
    return isEqual(root, root)
};

function isEqual(left, right) {
    if (left == null || right == null) return left == right;
    if (left.val != right.val) return false;
    return isEqual(left.left, right.right) && isEqual(left.right, right.left);
}

226. 翻转二叉树

反转

var invertTree = function(root) {
    if (root == null) return root;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

112. 路径总和

var hasPathSum = function(root, sum) {
    if (root == null) return false;
    sum -= root.val;
    // 递归边界
    if (root.left == null && root.right == null && sum == 0) return true;
    // 递归
    if (root.left != null && hasPathSum(root.left, sum)) return true;
    if (root.right != null && hasPathSum(root.right, sum)) return true;
    return false;
};

114. 二叉树展开为链表

var flatten = function(root) {
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

    let right = root.right;

    root.right = root.left;
    root.left = null;

    while (root.right != null) {
        root = root.right;
    }
    root.right = right;
};

练习：复杂递归

236. 二叉树的最近公共祖先（剑指 Offer 68 - II. 二叉树的最近公共祖先）

终止条件
- 空节点
- 当前节点为查找节点
递推公式
- 递归左子树
- 递归右子树

返回值

同时不为空，表示分居两侧
左侧不为空，左子树

右侧不为空，右子树

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

练习2: 遍历树与生成树

102. 二叉树的层序遍历

var levelOrder = function(root) {
    if (root == null) return []; 
    let res = [];
    let nodes = [root];
    while (nodes.length > 0) {
        let curLevel = [];
        let tmp = [];
        for (let node of nodes) {
            curLevel.push(node.val);
            node.left != null && tmp.push(node.left);
            node.right != null && tmp.push(node.right);
        }
        res.push(curLevel);
        nodes = tmp;
    }
    return res;
};

637. 二叉树的层平均值

654. 最大二叉树（数组构建的最大二叉树）

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。

右子树是通过数组中最大值右边部分构造出的最大二叉树。

var constructMaximumBinaryTree = function(nums) {
 let len = nums.length;
 if (len == 0) return null;
 if (len == 1) return new TreeNode(nums[0]);
 let maxNum = nums[0];
 let curIndex = 0;
 for (let i = 0; i < len; i++) {
     if (nums[i] > maxNum) {
         maxNum = nums[i];
         curIndex = i;
     }
 }
 let root = new TreeNode(maxNum);
 root.left = constructMaximumBinaryTree(nums.slice(0, curIndex));
 root.right = constructMaximumBinaryTree(nums.slice(curIndex+1));
 return root;
};

105. 从前序与中序遍历序列构造二叉树/106. 从中序与后序遍历序列构造二叉树 (同105)

关键：找到中间节点的索引，如此分割递归
⚠️ arr.slice([begin[, end]])，返回一个由 begin 和 end 决定的原数组的浅拷贝（包括 begin，不包括end）的新数组

var buildTree = function(preorder, inorder) {
 if (preorder.length == 0) return null;
 let val = preorder[0];
 let index = inorder.indexOf(val);
 let root = new TreeNode(val);
 root.left = buildTree(preorder.slice(1, index+1), inorder.slice(0, index));
 root.right = buildTree(preorder.slice(index+1), inorder.slice(index+1))
 return root;
};

（先序遍历）114. 二叉树展开为链表

迭代（推荐）

function flatten(root: TreeNode | null): void {
    while (root != null) {
        if (root.left != null) {
            let pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            }
            pre.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        root = root.right;
    }
};

递归（不推荐）

function flatten(root: TreeNode | null): void {
    if (root == null) return;
    flatten(root.left);
    flatten(root.right);
    let right = root.right;
    root.right = root.left;
    root.left = null;
    while (root.right != null) {
        root = root.right;
    }
    root.right = right;
};

练习3:

剑指 Offer 55 - II. 平衡二叉树(110. 平衡二叉树)

如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

var isBalanced = function(root) {
    if (root == null) return true
    return isBalanced(root.left) && isBalanced(root.right) && Math.abs(depth(root.left) -  depth(root.right)) <= 1;
};

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

剑指 Offer 26. 树的子结构

var isSubStructure = function(A, B) {
    if (A == null || B == null) return false;
    return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
};

var isSame = function (A, B) {
    if (B == null) return true;
    if (A == null) return false;
    return A.val == B.val && isSame(A.left, B.left) && isSame(A.right, B.right)
}