Summary

Outline:

• 二叉树的深度优先搜索 DFS in Binary Tree

1.遍历问题 Preorder / Inorder / Postorder

2.分治算法 Introduce Divide Conquer Algorithm

3.非递归 遍历法 分治法 Non-recursion vs Traverse vs Divide Conquer

4.二叉搜索树 Binary Search Tree

---> Insert P85/ Remove P87/ Find / Validate P95

Find:

boolean isPresent(TreeNode root,int data){
    if(root==null) {return false;} 
    if(root.val==data) {return true;}
    if(root.val<data){ return isPresent(root.right);}
    return isPresent(root.left);     
}

• 二叉树的宽度优先搜索 BFS in Binary Tree

• 二叉树算法有两大类，一类是遍历二叉树的类型，一类是分解子问题的类型。

  前者较简单，只要运用二叉树的递归遍历框架即可；后者的关键在于明确递归函数的定义，然后利用这个定义。

1.DFS

Recursive:Traverse(Top down)-->Return in parameter;

Recursive:Divided Conquer(Bottom up)-->return in return value

Non-recursive: preorder(stack)--66

Non-recursive: Inorder(stack)--67

Non-recursive: Postorder(stack)--68

2.BFS

3.Binary Tree Maximum Path Sum

1.Root-leaf : return Math.max(left,right)+root.val;

2.Root-anyone (P475 node中可能有负数) P475:判断left 和right的正负，全负就只返回root.val,一方负就返回另一方+root.val，全正就取max(left,right)+root.val

3.Anyone--anyone P94:

4.Binary Tree Path Sum

1.(Easy)P376 root--leaf

2.(Easy)P246

3.(Hard)P472

5.Lowest Common Ancestor

1.(Medium)P88

2.(Easy)P474 多给了父节点作为参数

3.(Medium)P578 多了如果A或者B不存在的情况，设置HelperType检查aexist和b_exist.

基本思路：

当前节点为空|当前节点是A或者B=>返回当前节点

递归寻找A，B在左右子树中的位置 =>用left和right是否为空判断

A,B位于root左右两侧=>root是LCA=>left!=null && right!=null

否则就是left或者right

6.Binary Tree Longest Consecutive Sequence

1.(Easy)P595 必须是从父节点到子节点的顺序，不可逆

2.(Medium)P614 起始节点任意。

3.(Medium)P619 不是二叉树，是K叉树，起始节点任意。

7.Traverse vs Divide Conquer

• They are both Recursion Algorithm

• Result in parameter vs Result in return value

• Top down vs Bottom up

8.Binary Search Tree

A binary search tree is a tree data structure, in which elements are inserted and kept in order. Each

node in the BST contains exactly two children, one or both of which can be null. The special property

that makes a BST a search tree, and not just any old binary tree, is that the left child of any node is

less than or equal to its parent, and the right child is greater than or equal to its parent. The left and

right children of any node are also roots of BSTs themselves. Searching a binary search tree can be

performed in O(log n) time, assuming a well balanced BST. This is performed by going down the left

path if the target value is smaller than the current node, or going down the right path if the target value

is larger than the current node.

---> Insert P85/ Remove P87/ Find / Validate P95

Find:

boolean isPresent(TreeNode root,int data){
    if(root==null) {return false;} 
    if(root.val==data) {return true;}
    if(root.val<data){ return isPresent(root.right);}
    return isPresent(root.left);     
}

• 从定义出发：

• 左子树都比根节点小

• 右子树都比根节点大

• 如果存在重复元素，可以自行选择放到左子树还是右子树

• 从效果出发：

• 中序遍历 in-order traversal 是升序序列

• 如图，中序遍历为 1 2 3 4 5

• 性质：

• 如果一棵二叉树的中序遍历不是升序，则一定不是BST

• 如果一棵二叉树的中序遍历是升序，也未必是BST

• 当存在重复元素时，相同的数要么同时在左子树，要么同时在右子树，不能一边一个

•Binary search tree successor:

Given the root of a binary search tree and a value, find the "successor" of that value, even if the value

doesn't exist in the tree. The "successor" is defined as the node appearing immediately after the given

node when performing an in-order traversal.

_Solution:_We start off by moving down our binary search tree looking for the target value. There are two cases

that need to be considered when looking for the "successor" in a binary search tree.

1.The first is when our target value has a right child, the successor is simply the leftmost node in our target's right

subtree.

2.If our target doesn't have a right child, or our target doesn't exist, we must check the rightmost node in our left subtree. If it is less than our target, we have found our successor. Otherwise we need to move down the left subtree.

Time:O(logn) Space:O(1)

public class Solution {
2. private static Node getLeftMost(Node head) {
3. Node current = head;
4. while (current.left != null)
5. current = current.left;
6. return current;
7. }
8.
9. private static Node getRightMost(Node head) {
10. Node current = head;
11. while (current.right != null)
12. current = current.right;
13. return current;
14. }
15.
16. public static int getSuccessor(Node head, int target) {
17. Node current = head;
18. int successor = 0;
19. while (current != null) {
20. if (current.value < target && current.right != null)
21. current = current.right;
22. else if (current.value > target) {
23. if (current.left != null &&
24. getRightMost(current.left).value > target)
25. current = current.left;
26. else {
27. successor = current.value;
28. current = null;
29. }
30. } else {
31. if (current.right != null)
32. successor = getLeftMost(current.right).value;
33. current = null;
34. }
35. }
36. return successor;
37. }

所谓二叉搜索树（Binary Search Tree，简称 BST）大家应该都不陌生，它是一种特殊的二叉树。

特殊在哪里呢？简单来说就是：左小右大。

BST 的完整定义如下：

1、BST 中任意一个节点的左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。

2、BST 中任意一个节点的左右子树都是 BST。

有了 BST 的这种特性，就可以在二叉树中做类似二分搜索的操作，搜索一个元素的效率很高。

比如下面这就是一棵合法的二叉树：

对于 BST 相关的问题，你可能会经常看到类似下面这样的代码逻辑：

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

这个代码框架其实和二叉树的遍历框架差不多，无非就是利用了 BST 左小右大的特性而已。

接下来我们讲几道二叉搜索树的必知必会题目。

一、判断 BST 的合法性

这里是有坑的哦，我们按照刚才的思路，每个节点自己要做的事不就是比较自己和左右孩子吗？看起来应该这样写代码：

boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (root.left != null && root.val <= root.left.val)
        return false;
    if (root.right != null && root.val >= root.right.val)
        return false;

    return isValidBST(root.left)
        && isValidBST(root.right);
}

但是这个算法出现了错误，BST 的每个节点应该要小于右边子树的所有节点，下面这个二叉树显然不是 BST，因为节点 10 的右子树中有一个节点 6，但是我们的算法会把它判定为合法 BST：

出现问题的原因在于，对于每一个节点 root，代码值检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root 的整个左子树都要小于 root.val，整个右子树都要大于 root.val。

问题是，对于某一个节点 root，他只能管得了自己的左右子节点，怎么把 root 的约束传递给左右子树呢？

请看正确的代码：

boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。

在 BST 中搜索元素

力扣第 700 题「二叉搜索树中的搜索」就是让你在 BST 中搜索值为 target 的节点，函数签名如下：

TreeNode searchBST(TreeNode root, int target);

如果是在一棵普通的二叉树中寻找，可以这样写代码：

TreeNode searchBST(TreeNode root, int target);
    if (root == null) return null;
    if (root.val == target) return root;
    // 当前节点没找到就递归地去左右子树寻找
    TreeNode left = searchBST(root.left, target);
    TreeNode right = searchBST(root.right, target);

    return left != null ? left : right;
}

这样写完全正确，但这段代码相当于穷举了所有节点，适用于所有普通二叉树。那么应该如何充分利用信息，把 BST 这个「左小右大」的特性用上？

很简单，其实不需要递归地搜索两边，类似二分查找思想，根据 target 和 root.val 的大小比较，就能排除一边。我们把上面的思路稍稍改动：

TreeNode searchBST(TreeNode root, int target) {
    if (root == null) {
        return null;
    }
    // 去左子树搜索
    if (root.val > target) {
        return searchBST(root.left, target);
    }
    // 去右子树搜索
    if (root.val < target) {
        return searchBST(root.right, target);
    }
    return root;
}

在 BST 中插入一个数

对数据结构的操作无非遍历 + 访问，遍历就是「找」，访问就是「改」。具体到这个问题，插入一个数，就是先找到插入位置，然后进行插入操作。

上一个问题，我们总结了 BST 中的遍历框架，就是「找」的问题。直接套框架，加上「改」的操作即可。一旦涉及「改」，函数就要返回 TreeNode 类型，并且对递归调用的返回值进行接收。

TreeNode insertIntoBST(TreeNode root, int val) {
    // 找到空位置插入新节点
    if (root == null) return new TreeNode(val);
    // if (root.val == val)
    //     BST 中一般不会插入已存在元素
    if (root.val < val) 
        root.right = insertIntoBST(root.right, val);
    if (root.val > val) 
        root.left = insertIntoBST(root.left, val);
    return root;
}

三、在 BST 中删除一个数

这个问题稍微复杂，跟插入操作类似，先「找」再「改」，先把框架写出来再说：

TreeNode deleteNode(TreeNode root, int key) {
    if (root.val == key) {
        // 找到啦，进行删除
    } else if (root.val > key) {
        // 去左子树找
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // 去右子树找
        root.right = deleteNode(root.right, key);
    }
    return root;
}

找到目标节点了，比方说是节点 A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。

情况 1：A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了。

if (root.left == null && root.right == null)
    return null;

情况 2：A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。

// 排除了情况 1 之后
if (root.left == null) return root.right;
if (root.right == null) return root.left;

情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。

if (root.left != null && root.right != null) {
    // 找到右子树的最小节点
    TreeNode minNode = getMin(root.right);
    // 把 root 改成 minNode
    root.val = minNode.val;
    // 转而去删除 minNode
    root.right = deleteNode(root.right, minNode.val);
}

三种情况分析完毕，填入框架，简化一下代码：

TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        // 这两个 if 把情况 1 和 2 都正确处理了
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 处理情况 3
        // 获得右子树最小的节点
        TreeNode minNode = getMin(root.right);
        // 删除右子树最小的节点
        root.right = deleteNode(root.right, minNode.val);
        // 用右子树最小的节点替换 root 节点
        minNode.left = root.left;
        minNode.right = root.right;
        root = minNode;
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode getMin(TreeNode node) {
    // BST 最左边的就是最小的
    while (node.left != null) node = node.left;
    return node;
}

这样，删除操作就完成了。

注意一下，上述代码在处理情况 3 时通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点：

// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
minNode.left = root.left;
minNode.right = root.right;
root = minNode;

有的读者可能会疑惑，替换 root 节点为什么这么麻烦，直接改 val 字段不就行了？看起来还更简洁易懂：

// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
root.val = minNode.val;

仅对于这道算法题来说是可以的，但这样操作并不完美，我们一般不会通过修改节点内部的值来交换节点。

因为在实际应用中，BST 节点内部的数据域是用户自定义的，可以非常复杂，而 BST 作为数据结构（一个工具人），其操作应该和内部存储的数据域解耦，所以我们更倾向于使用指针操作来交换节点，根本没必要关心内部数据。

不过这里我们暂时忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层细化问题的思维方式。

最后总结

通过这篇文章，我们总结出了如下几个技巧：

1、如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。

2、在二叉树递归框架之上，扩展出一套 BST 代码框架：

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

3、根据代码框架掌握了 BST 的增删查改操作。

Least common ancestor:(P 88 延伸)

(Hard)Binary search tree path：

Given the root of a binary search tree and two values, write a function that returns the path between

the two values.

Solution:

综合题：先找到LCA，再向左向右找到path,合并。

We can reuse the code that we wrote in the least common ancestor problem, because the least

common ancestor will be the root of our path. Once we have the least common ancestor, we can

simply build a path to the value on the right, and a path to the value on the left, and combine the two to

get the path between the two nodes.

Complexity:

Time: O(n) where n is the length of the path

Space: O(n)

public static List<TreeNode> findShortestPath(TreeNode head, int x, int y) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if (root == null) {
            return result;
        }
        TreeNode common = LCA(head, x, y);
        List<TreeNode> left = findPath(common, x);
        List<TreeNode> right = findPath(common, y);
        //这里判断x,y大小来确定哪个是左边的路径，并把左边的最后一个节点remove掉，因为会和右边第一个重复。
        if (x < y) {
            left.remove(left.size()-1);
            result.addAll(left);
            result.addAll(right);
        }else{
            right.remove(right.size()-1);
            result.addAll(right);
            result.addAll(left);
        }
        return result;
    }

    public TreeNode LCA(TreeNode root, int x, int y) {
        if (root == null) {
            return root;
        }
        if (root.val > x && root.val >y) {
            return LCA(root.left, x, y);
        }
        else if (root.val < x && root.val < y) {
            return LCA(root.right, x, y);
        }
        else
            return root;
    }

    public List<TreeNode> findPath(TreeNode root, int x) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if (root.val == x) {
            result.add(root);
            return result;
        }
        //注意顺序，先把左边的加进去最后加root.
        if (root.val > x) {
            List<TreeNode> left = findPath(root.left, x);
            result.addAll(left);
            result.add(root);
        }
        //注意顺序，先加进root,再把right加进去。
        if (root.val < x) {
            result.add(head);
            List<TreeNode> right = findPath(root.right, x);            
            result.addAll(right);
        }
        return result;
    }

9. Merge Sort vs Quick Sort

本质上说：

• Quick Sort: Binary Tree Pre-order Traverse

• Merge Sort: Binary Tree Post-order Traverse & Divide conquer

Quick Sort 的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

快速排序的代码框架如下：先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？

void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

Merge Sort: 的逻辑，若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。

归并排序的代码框架如下：先对左右子数组排序，然后合并（类似合并有序链表的逻辑），你看这是不是二叉树的后序遍历框架？另外，这不就是传说中的分治算法嘛，不过如此呀。

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}