二叉树

练习

• maximum-depth-of-binary-tree
• balanced-binary-tree
• binary-tree-maximum-path-sum
• lowest-common-ancestor-of-a-binary-tree
• binary-tree-level-order-traversal
• binary-tree-level-order-traversal-ii
• binary-tree-zigzag-level-order-traversal
• validate-binary-search-tree
• insert-into-a-binary-search-tree

知识点

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点

• 以根访问顺序决定是什么遍历
• 左子树都是优先右子树

前序递归

function preorderTraversal(root)  {
    if (root == null) {
        return
    }
    // 先访问根再访问左右
    console.log(root.Val)
    preorderTraversal(root.Left)
    preorderTraversal(root.Right)
}

前序非递归

中序非递归

后序非递归

注意点

• 核心就是：根节点必须在右节点弹出之后，再弹出

DFS 深度搜索-从上到下

var preoderTraversal = function(root){
    let result = [];
  dfs(root,result);
  return result;
}
var dfs = function(root,result){
    if( root == null ) return;
  result.push(root.val);
  dfs(root.left, result);
  dfs(root.right, result);
}

DFS 深度搜索-从下向上-分治法

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

注意点：

DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

BFS 层次遍历

分治法应用

归并排序，典型的分治算法；分治，典型的递归结构。

适用场景

• 快速排序
• 归并排序
• 二叉树相关问题

分治算法可以分三步走：分解 -> 解决 -> 合并

1. 分解原问题为结构相同的子问题。
   
2. 分解到某个容易求解的边界之后，进行第归求解。
   
3. 将子问题的解合并成原问题的解。
   

function traversal(root){
        if(root == null) {
        // do something and return
    }
    // 分解
    let left = traversal(root.Left)
    let right = traversal(root.Right)
    //  解决 合并
    let result = Merge from left and right
    return result
}

典型示例

// V2：通过分治法遍历二叉树
function preorderTraversal(root) {
    let result = divideAndConquer(root)
    return result
}
function divideAndConquer(root *TreeNode) []int {
    let result = [];
    // 返回条件
    if (root == nil) {
        return result
    }
    // 分治(Divide)
    let left = divideAndConquer(root.Left)
    let right = divideAndConquer(root.Right)
    // 合并结果(Conquer)
    result.push(root.val)
    result.push(left);
    result.push(right)
    return result
}

归并排序

func MergeSort(nums []int) []int {
    return mergeSort(nums)
}
func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    // 分治法：divide 分为两段
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])
    // 合并两段数据
    result := merge(left, right)
    return result
}
func merge(left, right []int) (result []int) {
    // 两边数组合并游标
    l := 0
    r := 0
    // 注意不能越界
    for l < len(left) && r < len(right) {
        // 谁小合并谁
        if left[l] > right[r] {
            result = append(result, right[r])
            r++
        } else {
            result = append(result, left[l])
            l++
        }
    }
    // 剩余部分合并
    result = append(result, left[l:]...)
    result = append(result, right[r:]...)
    return
}

注意点

递归需要返回结果用于合并

快速排序

注意点：

快排由于是原地交换所以没有合并过程 传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃

常见题目示例

maximum-depth-of-binary-tree

maximum-depth-of-binary-tree

给定一个二叉树，找出其最大深度。

思路：分治法

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

balanced-binary-tree

balanced-binary-tree

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1，
因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据，
所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

var isBalanced = function(root) {
    if(root == null) return true;
    var left = isBalanced(root.left);
    var right = isBalanced(root.right);
    return Math.abs(helper(root.left) - helper(root.right) ) < 2 && left && right
};
var helper = function(root) {
    if(root == null) return 0;
    let left = helper(root.left);
    let right = helper(root.right);
    return Math.max(left,right) + 1;
}

注意

一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义

binary-tree-maximum-path-sum

binary-tree-maximum-path-sum

给定一个非空二叉树，返回其最大路径和。

思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可

var maxPathSum = function(root) {
    if(root == null) return 0;
    let max = -99999999999;
    function helper(root){
        if(root == null) return 0;
        let left = Math.max(helper(root.left),0);
        let right =  Math.max(helper(root.right),0);
        max = Math.max(left+right+root.val , max);
        return Math.max(left,right) + root.val;
    };
    helper(root);
    return max
};

lowest-common-ancestor-of-a-binary-tree

lowest-common-ancestor-of-a-binary-tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

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

BFS 层次应用

binary-tree-level-order-traversal

binary-tree-level-order-traversal

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）

思路：用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)）

var levelOrder = function(root) {
    let result = [];
    if(root === null) return result;
    let queue = [];
    queue.push({node: root, leval:0})
    while(queue.length) {
        let { node, leval} = queue.shift();
        if(!result[leval]) {
            result[leval] = []
        }
        result[leval].push(node.val);
        if(node.left) queue.push({node: node.left, leval: leval+1});
        if(node.right) queue.push({node: node.right, leval: leval+1})
    }
    return result;
};

binary-tree-level-order-traversal-ii

binary-tree-level-order-traversal-ii

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：在层级遍历的基础上，翻转一下结果即可

var levelOrderBottom = function(root) {
    let result = [];
    if(root === null) return result;
    let queue = [];
    queue.push({node: root, leval:0})
    while(queue.length) {
        let { node, leval} = queue.shift();
        if(!result[leval]) {
            result[leval] = []
        }
        result[leval].push(node.val);
        if(node.left) queue.push({node: node.left, leval: leval+1});
        if(node.right) queue.push({node: node.right, leval: leval+1})
    }
    return result.reverse();
};

binary-tree-zigzag-level-order-traversal

binary-tree-zigzag-level-order-traversal

给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

var zigzagLevelOrder = function(root) {
    let result = [];
    if(root === null) return result;
    let queue = [];
    queue.push({node: root, leval:0})
    while(queue.length) {
        let { node, leval} = queue.shift();
        if(!result[leval]) {
            result[leval] = []
        }
        if(leval % 2 ){
            result[leval].unshift(node.val);
        } else {
            result[leval].push(node.val);
        }
        if(node.left) queue.push({node: node.left, leval: leval+1});
        if(node.right) queue.push({node: node.right, leval: leval+1})
    }
    return result;
};

二叉搜索树应用

validate-binary-search-tree

validate-binary-search-tree

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路 1：中序遍历，检查结果列表是否已经有序

思路 2：分治法，判断左 MAX < 根 < 右 MIN

var isValidBST = function(root) {
    var helper = function(root, max, min){
        if(root == null) return true;
        if(max !== null && root.val >= max.val) return false;
        if(min !== null && root.val <= min.val) return false;
        return helper(root.left, root,min) && helper(root.right, max, root);
    };
    return helper(root,null,null);
};

insert-into-a-binary-search-tree

insert-into-a-binary-search-tree

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。

思路：找到最后一个叶子节点满足插入条件即可

var insertIntoBST = function(root, val) {
    if(root == null) {
        return new TreeNode(val)
    } else if (root.val > val) {
        root.left =  insertIntoBST(root.left,val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
};

总结

• 掌握二叉树递归与非递归遍历
• 理解 DFS 前序遍历与分治法
• 理解 BFS 层次遍历