1.深度优先搜索（一）

https://leetcode-cn.com/tag/depth-first-search/

题目汇总

98. 验证二叉搜索树中等

99. 恢复二叉搜索树困难（？？？）

100. 相同的树简单

101. 对称二叉树简单

104. 二叉树的最大深度简单

105. 从前序与中序遍历序列构造二叉树中等

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

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

109. 有序链表转换二叉搜索树中等

110. 平衡二叉树简单

98. 验证二叉搜索树中等

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
1.节点的左子树只包含小于当前节点的数。
2.节点的右子树只包含大于当前节点的数。
3.所有左子树和右子树自身必须也是二叉搜索树。

思路一：中序遍历

一个有效的二叉搜索树中序遍历的结果一定是递增的序列，利用这个特性，对给定的二叉树中序遍历，结果记录于list之中，检验list是否为严格的升序，若是则为true，反之false。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了36.63%的用户
    List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
        inOrder(root);
        for(int i=1;i<list.size();i++){
            if(list.get(i)<=list.get(i-1)){
                return false;
            }
        }
    return true;
    }
    public void inOrder(TreeNode root){
        if(root!=null){
            inOrder(root.left);
            list.add(root.val);
            inOrder(root.right);
        }
    }
}

思路二：递归

设置上下界，依次递归比较节点值。
以下代码来自官方解题https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    public boolean helper(TreeNode node, Integer lower, Integer upper){
        if(node == null){
            return true;
        }
        int val = node.val;
        if (lower != null && val <= lower) 
            return false;
        if (upper != null && val >= upper) 
            return false;
        //递归调用检查它的左右子树是否满足
        if (! helper(node.right, val, upper)) 
            return false;
        if (! helper(node.left, lower, val))
             return false;
        return true;
    }   
}

99. 恢复二叉搜索树困难

二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。

进阶:
使用 O(n) 空间复杂度的解法很容易实现。

思路：递归中序遍历

代码来自精选解题https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode x = null, y = null, pred = null;
    public void swap(TreeNode a, TreeNode b) {//交换两个节点
        int tmp = a.val;
        a.val = b.val;
        b.val = tmp;
    }

    public void findTwoSwapped(TreeNode root) {//找到两个交换节点
        if (root == null) return;
        findTwoSwapped(root.left);
        if (pred != null && root.val < pred.val) {
            y = root;
            if (x == null) x = pred;
            else return;
        }
        pred = root;
        findTwoSwapped(root.right);
   }

    public void recoverTree(TreeNode root) {
        findTwoSwapped(root);
        swap(x, y);
    }
}

100. 相同的树简单

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路：递归

dfs可以用递归来实现，dfs是一种算法，并不是具体实现，本题是用递归实现的dfs。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(p == null && q == null)
            return true;
        if(p == null || q == null)
            return false;
        if(p.val != q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
        }

    }
}

101. 对称二叉树简单

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。但是 [1,2,2,null,3,null,3] 则不是镜像对称的
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？

思路：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        return isSymmetrical(root, root);
    }
    boolean isSymmetrical(TreeNode root1,TreeNode root2){
        if(root1 == null&&root2 == null)
            return true;
        if(root1 == null||root2 == null)
            return false;
        if(root1.val != root2.val)
            return false;
        return isSymmetrical(root1.left, root2.right)&&isSymmetrical(root1.right,root2.left);
    }
}

104. 二叉树的最大深度简单

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。

思路：递归

如果一棵树只有一个节点，那么它的深度为1。如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1；如果既有左子树又有右子树，那么树的深度就是其左右子树深度的较大值再加1。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(root == null)
            return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        int result = 1 + ((leftDepth > rightDepth)?leftDepth:rightDepth);
        return result;
    }
}

105. 从前序与中序遍历序列构造二叉树中等

根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：[3,9,20,null,null,15,7]

思路：递归

根据中序遍历和前序遍历可以确定二叉树，具体过程为：
根据前序序列第一个结点确定根结点
根据根结点在中序序列中的位置分割出左右两个子序列
对左子树和右子树分别递归使用同样的方法继续分解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {//执行用时 :13 ms, 在所有 Java 提交中击败了21.30%的用户
        if(preorder.length==0||inorder.length==0)
            return null;
        TreeNode root = new TreeNode(preorder[0]);//根据前序遍历确定根节点
        int len = preorder.length;
        for(int i=0;i<len;i++){
            if(preorder[0] == inorder[i]){
                root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),
                            Arrays.copyOfRange(inorder,0,i));    
                root.right = buildTree(Arrays.copyOfRange(preorder,i+1,len),
                            Arrays.copyOfRange(inorder,i+1,len));
                            break;
            }
        }
    return root;
    }
}

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

根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：[3,9,20,null,null,15,7]

思路：递归

根据中序遍历和后序遍历可以确定二叉树，具体过程为：
根据后序序列最后一个结点确定根结点
根据根结点在中序序列中的位置分割出左右两个子序列
对左子树和右子树分别递归使用同样的方法继续分解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {//执行用时 :13 ms, 在所有 Java 提交中击败了17.65%的用户
        if(inorder.length == 0 || postorder.length == 0)
            return null;
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        for(int i=0;i<inorder.length;i++){
            if(postorder[postorder.length-1] == inorder[i]){
                root.left = buildTree(Arrays.copyOfRange(inorder,0,i),
                            Arrays.copyOfRange(postorder,0,i));
                root.right = buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),
                            Arrays.copyOfRange(postorder,i,postorder.length-1));
                break;
            }
        }
    return root;
    }
}

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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组：[-10,-3,0,5,9]
一个可能的答案是：[0,-3,9,-10,null,5]，它表示下面这个高度平衡二叉搜索树。

思路：递归

因为是一个按照升序排列的有序数组，转换成平衡二叉树，那么把根节点选为数组的中点即可，找到根节点，然后把数组一分为二成为左子树和右子树，进入递归即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        return buildTree(nums, 0, nums.length-1);
    }

    private TreeNode buildTree(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        //当构造节点的左右子树时，对递增数组进行拆分并进行递归调用
        int mid =  left + (right - left + 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, left, mid - 1);
        root.right = buildTree(nums, mid + 1, right);
        return root;
    }
}

109. 有序链表转换二叉搜索树中等

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

思路：递归

问题的关键是找到链表的中间元素，使用两个指针，慢指针每次向后移动一个节点，快指针每次移动两个节点。当快指针到链表的末尾时，慢指针正好访问到链表的中间元素，然后将链表从中间元素的左侧断开，递归调用即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {//执行用时 :1 ms, 在所有 Java 提交中击败了86.03%的用户
        if(head == null)    
            return null;
        if(head.next == null)
            return new TreeNode(head.val);
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;//快指针每次走两步
            slow = slow.next;//慢指针每次走一步
        }
        while(pre.next != slow){
            pre = pre.next;
        }
        TreeNode root = new TreeNode(slow.val);//找到根节点
        ListNode hRight = slow.next;
        pre.next = null;//断开链表
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(hRight);
        return root;
    } 
}

110. 平衡二叉树简单

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
示例 :
给定二叉树 [3,9,20,null,null,15,7]
返回 true

思路：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {//执行用时 :1 ms, 在所有 Java 提交中击败了99.78%的用户
        if(root == null)
            return true;
        if(Math.abs(Height(root.left) - Height(root.right)) > 1)
            return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int Height(TreeNode root){
        if(root == null)
            return 0;
        int leftHeight = Height(root.left) + 1;
        int rightHeight = Height(root.right) + 1;
        return leftHeight > rightHeight ? leftHeight : rightHeight;
    }
}