刷题6 剑指 Offer — DFS

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；
常见的 DFS ： 先序遍历、中序遍历、后序遍历；
前序遍历：输出顺序：根节点、左子树、右子树
中序遍历：输出顺序：左子树、根节点、右子树
后序遍历：输出顺序：左子树、右子树、根节点
常见的 BFS ： 层序遍历（即按层遍历）。

剑指 Offer 27. 二叉树的镜像

• 时间复杂度：O(n)，空间复杂度：O(n)
  https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsepg3/

例如输入：
      4
  2      7
1   3  6   9

镜像输出：
     4
  7     2
9   6  3   1

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

var mirrorTree = function(root) {
    let res = null;
    if(root != null){
        res =new TreeNode(root.val);
        res.left = mirrorTree(root.right);
        res.right = mirrorTree(root.left);
    }
    return res 
};

剑指 Offer 28. 对称的二叉树

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsrxq1/

• 时间复杂度：O(n)

  var isSymmetric = function(root) {
    if(root==null){
        return true;
    }
    return dfs(root.left,root.right)
  };
  var dfs = function(t1, t2){
    if(t1==null && t2==null) {return true}
    if(t1==null|| t2==null) {return false}
    if(t1.val != t2.val){return false}
    return dfs(t1.left,t2.right) && dfs(t1.right,t2.left)
  }

剑指 Offer 54. 二叉搜索树的第 k 大节点

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xspy85/

• 时间复杂度：O(n)，空间复杂度：O(1)
• 二叉搜索树：根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。
• 二叉搜索树的【中序遍历】为 【递增序列】，易得二叉搜索树的 【中序遍历倒序】 为 【递减序列】 。
  因此，求 “二叉搜索树第 k大的节点” 可转化为求 “此树的【中序遍历倒序】的第 k 个节点”。 中序遍历 为 “左、根、右” 顺序，倒序就是“右、根、左” 。
  时间复杂度：O(n)，空间复杂度：O(1)

  var nums;
  var res;
  var kthLargest = function(root, k) {
    nums = k
    dfs(root);
    return res;
  };
  var dfs = function(root){
    if(root == null){
        return;
    }
    dfs(root.right);
    if(nums == 0){
        return
    }
    nums --;
    if(nums==0){
        res = root.val
    }
    dfs(root.left)
  }

  剑指 Offer 55 - I. 二叉树的深度

  https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsaki2/
• 时间复杂度：O(n)，空间复杂度：O(1)

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