算法篇05、二叉树相关算法

本篇主要讲解二叉树相关的算法；由于数组和链表是线性结构，因此使用循环迭代就可以很容易解决，但二叉树是树状结构，相关的问题使用迭代很难解决，因此一般的解决方法都是递归方法；

前言 二叉树TreeNode节点介绍

首先介绍一下我们本篇使用到的二叉树的节点类，本篇二叉树主要是解决leetcode上相关问题，因此节点没有使用泛型，而是直接使用的int；如果是定义数据结构，那么就需要使用泛型来保存节点的信息了；

成员变量val表示节点中保存的信息，left节点表示左子树，right节点表示右子树；三个构造方法，无参、一个参数、三个参数；

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;
    }
}
复制代码

1、leetcode144–二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

例如：

输入：root = [1,null,2,3]
输出：[1,2,3]

题解如下所示，首先定义储存结果的List，然后在前序遍历的位置将节点值保存到result中，最后返回result即可；

//leetcode144 二叉树的前序遍历
List<Integer> result = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
	//递归终止
    if (root == null) {
        return result;
    }
    result.add(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    return result;
}
复制代码

2、二叉树前序遍历应用1–所有节点值加1

题解如下所示，将二叉树中所有节点的值加1，我们只需要在前序遍历的位置操作节点，让节点值自增即可；

//二叉树前序遍历应用
//二叉树所有节点的值加1
public void plusOne(TreeNode root) {
    if (root == null) {
        return;
    }
    root.val++;
    plusOne(root.left);
    plusOne(root.right);
}
复制代码

3、二叉树前序遍历应用2–判断两棵二叉树是否完全相同

题解如下所示，此题的递归终止条件分三种情况，如有两棵字数都为空了，说明相同；如果有一棵为空，另一棵还没为空，说明不相同；如果节点值不相同说明两棵树也不同；

递归过程比较简单，就是递归的调用去比较两棵树的左子树和右子树是否完全相同；

//二叉树前序遍历应用
//判断两棵二叉树是否完全相同
public boolean isSameTree(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 isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
}
复制代码

4、二叉树前序遍历应用–判断一棵二叉树是否是二分搜索树

二分搜索树是指二叉树中任一节点的值都大于左子树的所有节点值；并且小于右子树中的所有节点值；

因为min代表以root为根节点的二分搜索树的最小值；max代表以root为根节点的二分搜索树的最大值；所以在递归终止条件中root的值小于等于min就代表不是一棵二分搜索树；同理root的值大于等于max的值也代表不是一棵二分搜索树；

递归过程就是去递归的判断root节点的左子树和右子树是不是一棵二分搜索树；

//二叉树前序遍历应用
//判断一棵二叉树是否是二分搜索树
public boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

//min代表以root为根节点的二分搜索树的最小值；max代表以root为根节点的二分搜索树的最大值
private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
	//递归终止条件
    if (root == null) {
        return true;
    }
    if (min != null && root.val <= min.val) {
        return false;
    }
    if (max != null && root.val >= max.val) {
        return false;
    }

    return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
}
复制代码

5、leetcode94–二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

例如：

输入：root = [1,null,2,3]
输出：[1,3,2]

题解如下所示，首先创建保存结果的List，然后在二叉树中序遍历的地方将节点值保存起来，最后返回list即可；

//leetcode94 二叉树的中序遍历
List<Integer> result = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) {
        return result;
    }
    inorderTraversal(root.left);
    result.add(root.val);
    inorderTraversal(root.right);
    return result;
}
复制代码

6、leetcode145–二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

题解如下所示，类比前序遍历和中序遍历，后序遍历唯一的不同就是遍历的位置在递归调用左子树和右子树之后；

//leetcode145二叉树的后序遍历
List<Integer> result = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null) {
        return result;
    }
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    result.add(root.val);
    return result;
}
复制代码

7、leetcode102–二叉树的层序遍历

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

例如：

二叉树：[3,9,20,null,null,15,7]
结果：[[3],[9,20],[15,7]]

题解如下所示，二叉树的层序遍历主要是借助队列这种数据结构，应用队列先进先出的性质；

首先定义队列queue，然后将root添加到queue中；每次从queue中取出全部节点进行遍历，这代表一层，如果遍历到的节点的左孩子或者右孩子不为空，就将左孩子或者右孩子保存进队列queue中，等待下一次遍历队列，就又会保存到下一层的List中去，每遍历完一层就将本层的List保存到结果中去，最后队列为空也就遍历完成了，返回结果即可；

//leetcode102 二叉树的层序遍历
List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return res;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode remove = queue.remove();
            temp.add(remove.val);
            if (remove.left != null) {
                queue.add(remove.left);
            }
            if (remove.right != null) {
                queue.add(remove.right);
            }
        }
        res.add(temp);
    }
    return res;
}
复制代码

8、leetcode104–二叉树的最大深度

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。
复制代码

题解如下所示，理解起来也非常容易，递归终止条件表示当root为空时返回0，因为一颗空树高度就是0；

递归过程，先递归求解左子树的最大高度，然后递归求解右子树的最大高度，最后结果就是取左子树和右子树的高度的最大值加1即可，加1表示加上root自身的高度；

//leetcode104 二叉树的最大深度
//函数语义：求以root为根节点的二叉树的最大深度并将其返回
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int leftMaxDepth = maxDepth(root.left);
    int rightMaxDepth = maxDepth(root.right);
    return Math.max(leftMaxDepth, rightMaxDepth) + 1;
}
复制代码

9、leetcode226–翻转一棵二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1
复制代码

题解过程如下所示，递归终止条件当root==null时返回null，因为一棵空树翻转之后也是null；

递归过程跟数组中交换两个位置的值的思想完全一致，先保存root的右子树，然后将root的右子树指向root的左子树，最后将root的左子树指向暂存的root的右子树；后面就是递归的翻转root的左子树和右子树了，一直递归到root==null；最后返回root即可；

//leetcode226 翻转一棵二叉树
//函数语义：翻转以root为根节点的二叉树，并将翻转后的二叉树的根节点返回
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }

    TreeNode rightNode = root.right;
    root.right = root.left;
    root.left = rightNode;

    invertTree(root.left);
    invertTree(root.right);

    return root;
}
复制代码

10、leetcode112–路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

题解如下所示，递归终止条件返回true只有一种条件，那就是左右子树都为空，代表这是一个叶子节点，然后节点的值等于当前的target；

在递归过程中去递归的寻找root的左右子树，因为是在左右子树中找路径总和，因此此时的target就应该是原target减去当前root的值；如果有任意一遍返回true，说明存在这样一条路径，返回true；否则返回false说明不存在；

//leetcode112 路径总和
//函数语义：求以root为根节点的二叉树是否存在路径，满足路径上所有节点值的和为target
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null && root.val == targetSum) {
        return true;
    }

    if (hasPathSum(root.left, targetSum - root.val)
            || hasPathSum(root.right, targetSum - root.val)) {
        return true;
    }
    return false;
}
复制代码

11、leetcode257–二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
复制代码

题解如下所示，当前root的左右子树都为空时表示当前root是叶子节点了，此时把字符串存入结果中即可；当root不是叶子节点时，递归的调用当前root的左右子树去往字符串中添加路径上的值；

//leetcode257 二叉树的所有路径
public List<String> binaryTreePaths(TreeNode root) {
    List<String> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    solve(root, "", res);
    return res;
}

private void solve(TreeNode root, String cur, List<String> res) {
    if (root == null) {
        return;
    }
    cur = cur + root.val;
    if (root.left == null && root.right == null) {
        res.add(cur);
        return;
    }

    solve(root.left, cur + "->", res);
    solve(root.right, cur + "->", res);
}
复制代码

12、leetcode111–二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

题解如下所示，其实求二叉树的最小深度就是层序遍历的典型应用；当我们一层一层的遍历时，最先没有节点的那一层就是最短的那一层，也就是最小深度；因此跟层序遍历的逻辑完全相同，只不过是当循环到的节点左右子树都为空的时候直接返回，因为左右子树都为空了表示就是叶子节点了；

//leetcode 111 二叉树的最小深度 广度优先遍历的典型应用
public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int depth = 1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode remove = queue.remove();
            if (remove.left == null && remove.right == null) {
                return depth;
            }
            if (remove.left != null) {
                queue.add(remove.left);
            }
            if (remove.right != null) {
                queue.add(remove.right);
            }
        }
        depth++;
    }
    return depth;
}
复制代码

13、leetcode235–二分搜索树的最近公共祖先

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

题解如下所示，递归终止条件，当某个节点等于root节点时，直接返回当前节点；

递归过程，我们利用二分搜索树的性质，当p、q的值都比root的值大的话，那么最近公共祖先一定在root的右子树中，因此递归的去右子树中寻找；同理p、q的值都比root的值小的话，那么最近公共祖先一定在root的左子树中；其他情况就说明一个比root大，一个比root小，因此最近公共祖先一定是root；

//leetcode235 二分搜索树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val == root.val) {
        return p;
    }
    if (q.val == root.val) {
        return q;
    }

    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else {
        return root;
    }
}
复制代码

下面是二分搜索树的几个常规操作

14、在二分搜索树中查找一个数是否存在

题解如下所示，当递归到底root==null了说明没有找到返回false，如果递归过程中当前root的值等于target返回true；如果当前root的值比target大，那么就递归的去当前root的左子树去找，否则递归的去右子树找；

//在二分搜索树中查找一个数是否存在，我们可以利用二分搜索树的性质进行递归
public boolean isInBST(TreeNode root, int target) {
    if (root == null) {
        return false;
    }
    if (root.val == target) {
        return true;
    }

    if (target < root.val) {
        return isInBST(root.left, target);
    } else {
        return isInBST(root.right, target);
    }
}
复制代码

15、向二分搜索树中插入一个数

题解如下所示，这里我们默认不能保存重复元素，所以当前root的val等于target时直接返回当前root；当root==null了说明递归到底了，直接新建节点返回即可；递归过程中当添加的元素比当前root大时，添加到当前root的右子树中；当添加的元素比当前root小时，添加到root的左子树中；

//向二分搜索树中插入一个数,并返回新的二分搜索树的根节点
public TreeNode insertIntoBST(TreeNode root, int target) {
    if (root == null) {
        return new TreeNode(target);
    }
    if (root.val == target) {
        return root;
    }

    if (root.val < target) {
        root.right = insertIntoBST(root.right, target);
    }
    if (root.val > target) {
        root.left = insertIntoBST(root.left, target);
    }
    return root;
}
复制代码

16、从二分搜索树中删除节点

从二分搜索树中删除节点是最麻烦的操作，因为删除元素分几种不同的情况，并且删除完元素还要保持二分搜索树的结构；

当当前root的值等于target时就表示当前root时待删除的节点；否则就继续递归的去左右子树中查找待删除的节点；

当找到待删除的节点时又分三种情况；当待删除的节点左右子树都为空时表示这是一棵叶子节点，删除后直接返回null就行；当待删除的节点的左右子树有一边为空时，删除后需要将不为空的另一边返回来替代被删除的位置；当待删除的节点的左右子树都不为空时，首先找到待删除节点的右子树中最小的那个节点，然后将待删除节点的值修改为右子树中最小的节点的值，最后将待删除节点的右子树中最小的节点删除，右子树的最小节点的左子树一定为空，所以就转化为上边第二种情况的删除了；

其实这里用了一点技巧，就是将待删除节点的右子树中最小节点的值替换为待删除节点，然后去把最小节点删除了，其实并没有删除那个待删除的节点；但是当Node节点数据结构中保存的信息很复杂时，我们就不能通过这种修改节点信息的方式删除了，就应该修改指针的指向，执行真正的删除操作；

//从二分搜索树中删除节点,并返回新的二分搜索树的根节点
//删除节点分三种情况
public TreeNode deleteNode(TreeNode root, int target) {
    if (root == null) {
        return null;
    }
    if (root.val == target) {
        //情况1，待删除节点的左右子树都为空，直接删除
        if (root.left == null && root.right == null) {
            return null;
        }
        //情况2，待删除节点的左子树或者右子树为空
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        //情况3，待删除节点的左右子树都不为空
        TreeNode rightMin = minNode(root.right);
        root.val = rightMin.val;
        root.right = deleteNode(root.right, rightMin.val);
    }

    if (root.val < target) {
        root.right = deleteNode(root.right, target);
    }
    if (root.val > target) {
        root.left = deleteNode(root.left, target);
    }
    return root;
}

private TreeNode minNode(TreeNode root) {
    while (root.left != null) {
        root = root.left;
    }
    return root;
}
复制代码

题目来源出处：

来源：力扣（LeetCode）
链接：leetcode-cn.com/problemset/…