leetcode_二叉树_递归
二叉树 递归
总结：二叉树具有天然的递归结构，因为二叉树的定义本身就是个递归地定义过程，而递归我们需要把握住三点，第一是递归函数<mark>及其传参</mark>的含义（就像数组的边界定义，链表的所有引用的含义一样重要）；第二是递归的终止条件；第三是递归过程（递归过程可能涉及递归函数的调用以及其它的计算）。
需要注意的是，如果递归有返回值，可以通过返回值进行很多处理，可以替代一些传参，往往一些比较简单的递归这么去做逻辑比较清晰；而像比较复杂度回溯处理的递归问题，不要返回值，而是通过传参处理逻辑会比较清晰。
实际上返回值可以替代一个传参（只是一个），但是当递归函数需要很多传参才可以解决问题时仅仅一个返回值是实现不了的，这时如果结合返回值和传参会使逻辑比较混乱，不如就只是用传参。
1. 104 二叉树的最大深度
- 方法：递归解决。
/** * 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) {
// 由于当前节点为null 根据递归函数的含义，空树的最大深度为0
if(root == null)
return 0;
// 得到左右子树的最大深度
int leftMaxDepth = maxDepth(root.left);
int rightMaxDepth = maxDepth(root.right);
return Math.max(leftMaxDepth, rightMaxDepth) + 1;
}
}
2. 111 二叉树的最小深度
- 方法：递归解决。有一个陷阱，由于题目要求的是从根节点到叶子节点的最短路径，因此要防止根节点的某个子树为空的情况。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
// 递归函数的含义是计算以当前节点为根节点的树的最小深度
public int minDepth(TreeNode root) {
// 根据递归函数的定义，空树的最小深度是0
if(root == null)
return 0;
int leftMinDepth = minDepth(root.left);
int rightMinDepth = minDepth(root.right);
int min = 0;
if(leftMinDepth == 0)
min = rightMinDepth;
else if(rightMinDepth == 0)
min = leftMinDepth;
else
min = Math.min(leftMinDepth, rightMinDepth);
return min + 1;
}
}
3. 226 翻转二叉树
- 方法：递归函数的含义是将传入的当前节点作为根节点，翻转左右子树。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
// 翻转当前节点的左右子节点
swap(root);
// 翻转左子树，翻转右子树
invertTree(root.left);
invertTree(root.right);
return root;
}
// 交换节点root的左右子节点的值
private void swap(TreeNode root){
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
4. 100 相同的树
- 方法：递归函数的含义，判断传入的两个节点是否相同，包括是否类型相同即是否为null以及值是否相同。递归终止条件，不相同时返回false，否则继续递归调用；都是null时返回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 isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(!isSameNode(p, q))
return false;
if(isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
return true;
return false;
}
private boolean isSameNode(TreeNode p, TreeNode q){
if(p == null && q != null || p != null && q == null)
return false;
if(p == null && q == null || p.val == q.val)
return true;
return false;
}
}
5. 101 对称二叉树
- 方法：判断二叉树是否对称，实际上拆解来看，就是判断根节点的两个子树是否对称相同，判断其两个子树是否对称时就是将这个两个子树看做两个不同的树来判断，和根节点就没关系了。
/** * 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) {
if(root == null)
return true;
return isSymmetricTree(root.left, root.right);
}
// 判断两个树是否对称
private boolean isSymmetricTree(TreeNode root1, TreeNode root2){
if(root1 == null && root2 != null || root1 != null && root2 == null)
return false;
if(root1 == null && root2 == null)
return true;
if(root1.val == root2.val)
return isSymmetricTree(root1.left, root2.right) && isSymmetricTree(root1.right, root2.left);
return false;
}
// 判断两个节点是否相同
private boolean isSameNode(TreeNode p, TreeNode q){
if(p == null && q != null || p != null && q == null)
return false;
if(p == null && q == null || p.val == q.val)
return true;
return false;
}
}
6. 222 完全二叉树的节点个数
- 方法：递归函数的含义，计算以传入的节点为根节点的树的节点总数。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int countNodes(TreeNode root) {
if(root == null)
return 0;
int result = 1;
result += countNodes(root.left);
result += countNodes(root.right);
return result;
}
}
7. 110 平衡二叉树
- 方法：递归函数的含义，判断当前节点为根节点的树是否平衡，并有一个方法递归地计算以传入的节点为根节点的树的高度。
/** * 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) {
if(root == null)
return true;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if(Math.abs(leftHeight - rightHeight) <= 1)
return isBalanced(root.left) && isBalanced(root.right);
return false;
}
private int getHeight(TreeNode node){
if(node == null)
return 0;
int result = 1;
result += Math.max(getHeight(node.left), getHeight(node.right));
return result;
}
}
8. 404 左叶子之和
- 方法：递归函数的含义，以当前节点为根节点的树，计算其左叶子之和。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null)
return 0;
// 判断是否为左叶子节点并将所有左叶子节点求和值
int result = 0;
if(root.left != null && root.left.left == null && root.left.right == null)
result += root.left.val;
// root为根节点，要计算出其所有左叶子节点的和，需要计算root的左子树中左叶子节点的和
// 以及root的右子树中左叶子节点的和
if(root.left != null)
result += sumOfLeftLeaves(root.left);
if(root.right != null)
result += sumOfLeftLeaves(root.right);
return result;
}
}
9. 257 二叉树的所有路径
- 方法：递归，首先定义好递归函数的含义，这里递归函数就是将传入的root当做一个二叉树的根节点，返回其所有路径组成的字符串；其次，自然而然地根据递归函数的定义就得到递归终止条件，当root为null时没有任何字符串能够返回，则返回空的list，当root为叶子节点时，只有叶子的值单做字符串的字符返回即可；最后递归的递归过程，就是得到左子树的所有路径，以及得到右子树的所有路径，然后通过当前节点的值组合得到所有的路径，并返回。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if(root == null)
return result;
if(root.left == null && root.right == null){
result.add(String.valueOf(root.val));
return result;
}
List<String> leftStrings = binaryTreePaths(root.left);
for(String str : leftStrings)
result.add(String.valueOf(root.val) + "->" + str);
List<String> rightStrings = binaryTreePaths(root.right);
for(String str : rightStrings)
result.add(String.valueOf(root.val) + "->" + str);
return result;
}
}
10. 112 路径总和
- 注意递归的终止条件。
- 方法：递归。弄清楚递归函数的含义：hasPathSum(TreeNode root, int sum)是判断传入的根节点到叶子节点是否有路径其所有节点和为sum。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
// 当root节点为null，是没有val的，因此无法判断是否值为sum，直接返回false
if(root == null)
return false;
// 当root节点的左右子树都是null时，说明此节点是一个叶子节点，叶子节点才有资格判断是否达到和为sum
// 因为题目要找的是根节点到叶子节点的路径和为sum
if(root.left == null && root.right == null)
return root.val == sum;
if(hasPathSum(root.left, sum - root.val))
return true;
if(hasPathSum(root.right, sum - root.val))
return true;
return false;
}
}
11. 113 路径总和II
- 方法：递归函数的含义，以传入的节点root为根节点的树，求出所有的和为传入值sum的路径，
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null)
return new ArrayList<>();
// 如果是根节点则找到一条路径，判断是否满足和为sum
if(root.left == null && root.right == null){
if(root.val == sum){
List<Integer> list = new ArrayList<>();
list.add(root.val);
List<List<Integer>> result = new ArrayList<>();
result.add(list);
return result;
}else
return new ArrayList<List<Integer>>();
}
// 不是根节点则继续下面处理，从其左右子树中分别去找路径
List<List<Integer>> leftPath = pathSum(root.left, sum - root.val);
List<List<Integer>> rightPath = pathSum(root.right, sum - root.val);
List<List<Integer>> result = new ArrayList<>();
for(List<Integer> list : leftPath){
list.add(0, root.val);
result.add(list);
}
for(List<Integer> list : rightPath){
list.add(0, root.val);
result.add(list);
}
return result;
}
}
12. 437 路径总和III
- 方法：递归，弄清楚递归的函数含义，由于题目要求返回所有的路径，路径不一定是从根节点开始，也不一定是在叶子节点结束，因此对于某个节点要分包括这个节点的所有路径和不包括这个节点的所有路径。
- 复杂的递归逻辑。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
// 给定节点node，以node为根节点所组成的二叉树的所有不一定包括node节点的和为sum的路径数
public int pathSum(TreeNode root, int sum) {
if(root == null)
return 0;
int result = 0;
// 包括root节点的路径
result += findPath(root, sum);
//不包括root节点的路径
result += pathSum(root.left, sum);
result += pathSum(root.right, sum);
return result;
}
// 给定节点node，以node为根节点所组成的二叉树的所有包括node节点的和为num的路径数
private int findPath(TreeNode node, int num){
if(node == null)
return 0;
int result = 0;
if(node.val == num)
result += 1;
result += findPath(node.left, num - node.val);
result += findPath(node.right, num - node.val);
return result;
}
}
13. 129 求根到叶子节点数字之和
- 方法：定义如下递归函数，List allPathNumber(TreeNode node)，以传入的节点为树的根节点，计算返回该树的所有从根节点到叶子节点路径组成的数字字符串，int sumNumbers(TreeNode root)方法调用上述方法得到所有路径组成的数字，将这些数字求和得到结果。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int sumNumbers(TreeNode root) {
List<String> list = allPathNumber(root);
int result = 0;
for(String str : list){
int temp = Integer.valueOf(str);
result += temp;
}
return result;
}
private List<String> allPathNumber(TreeNode node){
if(node == null)
return new ArrayList<String>();
if(node.left == null && node.right == null){
List<String> list = new ArrayList<>();
list.add(String.valueOf(node.val));
return list;
}
List<String> result = new ArrayList<>();
List<String> leftAllPathNumber = allPathNumber(node.left);
List<String> rightAllPathNumber = allPathNumber(node.right);
for(String str : leftAllPathNumber){
StringBuilder sb = new StringBuilder(str);
sb.insert(0, node.val);
result.add(sb.toString());
}
for(String str : rightAllPathNumber){
StringBuilder sb = new StringBuilder(str);
sb.insert(0, node.val);
result.add(sb.toString());
}
return result;
}
}
14. 938 二叉搜索树的范围和
- 方法：递归，想清楚递归函数的含义，根据这个含义想清楚递归终止条件，然后根据终止条件和递归函数的含义想清楚递归过程，这个题就解决了。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
// 递归函数rangeSumBST(TreeNode root, int L, int R)的含义如下
// 在以传入的root为根节点的树中，计算所有节点值在[L, R]区间中的节点的值的和
public int rangeSumBST(TreeNode root, int L, int R) {
if(root == null)
return 0;
int result = 0;
if(root.val < L)
result += rangeSumBST(root.right, L, R);
if(root.val > R)
result += rangeSumBST(root.left, L, R);
if(root.val <= R && root.val >= L){
result += root.val;
result += rangeSumBST(root.left, L, R);
result += rangeSumBST(root.right, L, R);
}
return result;
}
}
15. 894 所有可能的满二叉树
- 方法：递归构造满二叉树，一定要弄清楚递归函数的含义，在这里递归函数 List allPossibleFBT(int N) 表示，传入节点数N，构造所有可能的总节点数为N的满二叉树，并将这些二叉树的根节点组成list返回。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public List<TreeNode> allPossibleFBT(int N) {
// 递归终止条件
// 当N为0时，根据递归函数的含义，节点数为0的满二叉树不存在，因此返回空list
if(N == 0)
return new ArrayList<TreeNode>(0);
// 当N为1时，根据递归函数的含义，节点数为1的满二叉树只有一种可能，就是该节点就是根节点的树，因此返回list只包含这一个树
if(N == 1){
TreeNode root = new TreeNode(0);
root.left = null;
root.right = null;
List<TreeNode> result = new ArrayList<>();
result.add(root);
return result;
}
// 递归过程，考虑到奇数个节点才能组成一个满二叉树，而所有子树的节点树有多种不同的分配方式，通过for循环遍历所有的可能
List<TreeNode> result = new ArrayList<>();
N--;
for(int i = 1; i < N; i += 2){
List<TreeNode> leftAllFBT = allPossibleFBT(i);
List<TreeNode> rightAllFBT = allPossibleFBT(N - i);
for(TreeNode x : leftAllFBT){
for(TreeNode y : rightAllFBT){
TreeNode root = new TreeNode(0);
root.left = x;
root.right = y;
result.add(root);
}
}
}
return result;
}
}
16. 98 验证二叉搜索树
- 有问题的方法：递归函数的含义，以当前传入的节点为根节点的树，验证该树是否为二叉搜索树，刚开始想的方法有问题，只是比较了某个节点大于左子节点并小于右子节点，但是可能会出现某节点大于右子节点的左子节点，这是不符合二叉搜索树的定义的
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
if(root.left != null && root.right != null){
if(root.val <= root.left.val && root.val >= root.right.val)
return false;
return isValidBST(root.left) && isValidBST(root.right);
}
else if(root.left == null && root.right != null){
if(root.val >= root.right.val)
return false;
return isValidBST(root.right);
}
else if(root.left != null && root.right == null){
if(root.val <= root.left.val)
return false;
return isValidBST(root.left);
}
return true;
}
}
- 正确解法一：上面的问题在于某个节点不仅要小于其右子节点，而且要小于其右子树的所有节点，并且大于左子树的所有节点，因此我们改变比较的方式，不是比较当前节点值和左右子节点的值大小，而是传入一个当前节点值的范围上下界，对于根节点，根节点的值是多少都可以，只要其左右子树满足二叉搜索树的定义即可，因此根节点的范围为null，定义递归函数的含义为传入一个节点，以及该几点的上下界，判断以当前节点为根节点的树是否为二叉搜索树。时间复杂度和空间复杂度都是O(n)。
- 这种方法通过上下界刚好避免了上面解法碰到的问题，即root.val < root.right.val 但是 root.val > root.right.left.val
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean isValidBSTByLimits(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 (!isValidBSTByLimits(node.right, val, upper))
return false;
if (!isValidBSTByLimits(node.left, lower, val))
return false;
return true;
}
public boolean isValidBST(TreeNode root) {
return isValidBSTByLimits(root, null, null);
}
}
- 解法二：中序遍历二叉搜索树，正常的二叉搜索树中序遍历是递增的，判断得到的序列是不是递增的即可判断是否为有效的二叉搜索树。时间复杂度比较高。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = getAllValByMiddle(root);
for(int i = 0; i < list.size(); i++){
int j = i + 1;
if(j < list.size() && list.get(i) >= list.get(j))
return false;
}
return true;
}
private List<Integer> getAllValByMiddle(TreeNode node){
if(node == null)
return new ArrayList<Integer>();
List<Integer> leftList = getAllValByMiddle(node.left);
leftList.add(node.val);
List<Integer> rightList = getAllValByMiddle(node.right);
for(Integer x : rightList)
leftList.add(x);
return leftList;
}
}
17. 450 删除二叉搜索树中的节点
- 方法：要删除一个节点，首先递归找到这个节点，然后删除这个节点，删除该节点时要保持二叉搜索树的特性，因此可以找该节点的左子树的最大值和该节点值交换并删除最大值节点，或者找该节点的右子树的最小值和该节点值交换并删除最小值节点。但是如何删除这个最大值或者最小值节点呢？当前节点不是要删除的节点时则在其左子树或者右子树中删除，如果当前节点就是要删除的节点，则有三种情况，如果当前节点时叶子节点，则当前节点直接删除返回null即可；如果当前节点左右子树中有一个是null则不是null的子树根节点就是新的当前树的根节点；如果当前节点的左右子树都不是null，则需要将左子树的最大值或者右子树的最小值作为该节点的替代，并调整子树，这里以右子树的最小值作为该节点的替代，调整子树即删除子树中值为该最小值的节点。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
// 递归函数含义，以root为根节点，key为目标值，寻找并删除值等于key的节点，并返回删除根节点且调整结构后的树的根节点
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null)
return null;
if(root.val > key)
root.left = deleteNode(root.left, key);
else if(root.val < key)
root.right = deleteNode(root.right, key);
else{
// 当前节点就是要删除的节点
// 当前节点为叶子节点
if(root.left == null && root.right == null)
return null;
// 当前节点的左右子树中有一个是null
else if(root.left != null && root.right == null)
return root.left;
else if(root.left == null && root.right != null)
return root.right;
// 当前节点的左右子树均不为null
else{
// 找到右子树的最小值
TreeNode temp = root.right;
int min = temp.val;
while(temp != null){
min = temp.val;
temp = temp.left;
}
// 当前节点赋值为右子树最小值
// 删除右子树中值为该最小值的节点
root.val = min;
root.right = deleteNode(root.right, min);
}
}
return root;
}
}
18. 108 将有序数组转换为二叉搜索树
- 方法：以数组中间节点为根节点的值，递归构造二叉搜索树
/** * 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) {
if(nums.length == 0)
return null;
int mid = nums.length / 2;
TreeNode root = new TreeNode(nums[mid]);
int[] leftNums = Arrays.copyOfRange(nums, 0, mid);
int[] rightNums = Arrays.copyOfRange(nums, mid + 1, nums.length);
root.left = sortedArrayToBST(leftNums);
root.right = sortedArrayToBST(rightNums);
return root;
}
}
19. 230 二叉搜索树中第K小的元素
- 方法一：中序遍历二叉搜索树，得到从小到大的排列数据，然后获取第k大的。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public int kthSmallest(TreeNode root, int k) {
ArrayList<Integer> numbers = getAllNumbersByMid(root);
return numbers.get(k - 1);
}
private ArrayList<Integer> getAllNumbersByMid(TreeNode node){
if(node == null)
return new ArrayList<Integer>();
ArrayList<Integer> left = getAllNumbersByMid(node.left);
ArrayList<Integer> result = new ArrayList<>();
for(Integer x : left)
result.add(x);
result.add(node.val);
ArrayList<Integer> right = getAllNumbersByMid(node.right);
for(Integer x : right)
result.add(x);
return result;
}
}
方法二：优化上述方法，上面的方***将所有的数据都读取出来，实际上对于二叉搜索树不需要读取所有的数据，当读取到第k大的数据时，就可以停下来了。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
int count = 0;
public int kthSmallest(TreeNode root, int k) {
return (int)finKthSmallest(root, k);
}
private Integer finKthSmallest(TreeNode node, int k){
if(node == null)
return null;
Integer left = finKthSmallest(node.left, k);
if(left != null)
return left;
if((++count) == k)
return new Integer(node.val);
Integer right = finKthSmallest(node.right, k);
if(right != null)
return right;
return null;
}
}
20. 235 二叉搜索树的最近公共祖先
- 方法：递归查找，递归函数的含义是在以传入的root为根节点的树中查找传入的两个节点的公共祖先。如果搜索的两个值在当前节点node的一侧，则需要递归查找该侧子树，否则无论是两个值在当前节点node的两侧还是其中一个值就是当前节点，公共祖先都是当前节点。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
if(p.val < root.val && q.val > root.val || p.val > root.val && q.val < root.val || p.val == root.val || q.val == root.val)
return root;
if(p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
if(p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
return null;
}
}
21. 236 二叉树的最近公共祖先
- 这道题不同于二叉搜索树的最近公共祖先，在二叉搜索树中可以利用其特殊结构，即当前节点的值一定大于左子树的所有节点值，当前节点的值一定小于右子树的所有节点值，通过这个特点能够判断pq两个节点是在当前节点的一侧还是在当前节点的两侧。
- 方法：递归函数的含义，以输入的root节点为根节点，查找pq的最近公共祖先，如果当前节点是null则返回null，如果当前节点和pq中的某个节点相等，则当前节点就是最近公共祖先；如果当前节点和pq都不相等，则有两种情况分别是，pq在当前节点的两侧，则当前节点就是最近公共祖先，如果pq在单侧则在该侧找到最近公共祖先。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
// 当前节点和pq中某一个相等
if(root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// pq在当前节点的两侧
if(left != null && right != null)
return root;
// pq在当前节点的某一单侧
return left != null ? left : right;
}
}
22. 二叉树的非递归遍历总结
/** * * *非递归遍历 * * */
public class BinaryTree{
//先序遍历，且为根左右
public void preOrder(Node root){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
//先处理根节点
System.out.println(cur.Value);
//后处理左右子节点，由于是根左右的顺序，因此先处理左节点，要先入栈右节点
if(cur.rightChild != null)
stack.push(cur.rightChild);
if(cur.leftChild != null)
stack.push(cur.leftChild);
}
}
//中序遍历，且为左根右
public void midOrder(Node root){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
Node myRoot = root;
while(!stack.isEmpty() || myRoot != null){
if(myRoot != null){
stack.push(myRoot);
myRoot = myRoot.leftChild;
}else{
myRoot = stack.pop();
System.out.println(myRoot.value);
myRoot = myRoot.rightChild;
}
}
}
//后续遍历，且为左右根
//两个栈实现
//栈2保存最后可以直接按顺序输出的值
//栈1作为中间容器，实现栈2按顺序保存树的值
public void posOrder(Node root){
if(root == null)
return;
Stack<Node> stackOne = new Stack<>();
Stack<Node> stackTwo = new Stack<>();
stackOne.push(root);
while(!stackOne.isEmpty()){
Node cur = stackOne.pop();
stackTwo.push(cur);
if(cur.leftChild != null)
stackOne.push(cur.leftChild);
if(cur.rightChild != null)
stackOne.push(cur.rightChild);
}
while(!stackTwo.isEmpty()){
Node cur = stackTwo.pop();
System.out.println(cur.value);
}
}
//一个栈实现后续遍历
//栈中保存一个子树的左子节点和根节点，这样可以先处理左子节点然后通过根节点处理右子节点，最后处理根节点
public void posOrder2(Node root){
if(root == null)
return;
Stack<Node> stack = new Stack<>();
Node curNode = root;
Node lastNode = null;
while(curNode != null){
stack.push(curNode);
curNode = curNode.leftChild;
}
while(!stack.isEmpty()){
curNode = stack.pop();
//有右子树并且右子树不是上一次刚处理过，则不处理当前的根节点，当前根节点需要入栈，要先处理右子树才可以处理当前根节点
//否则可以处理当前根节点
if(curNode.rightChild != null && curNode.rightChild != lastNode){
stack.push(curNode);
curNode = curNode.rightChild;
//因为是处理右子树，故仍需要将该右子树的左节点入栈
while(curNode != null){
stack.push(curNode);
curNode = curNode.leftChild;
}
}else{
//处理当前根节点
System.out.println(curNode.value);
lastNode = curNode;
}
}
}
}
class Node{
public int value;
public Node leftChild;
public Node rightChild;
public Node(int value){
this(value, null, null);
}
public Node(int value, Node leftChild, Node rightChild){
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
递归问题
1. 794. 有效的井字游戏
-
井字游戏介绍：题目要求第一步先出X，按照X O的顺序依次出棋子，棋盘3 * 3，如果任意一行或者一列或者两个对角线之一的棋子为相同棋子则游戏结束。
-
方法：递归，题目给了一个初始的井字游戏棋盘，其中放置了一些棋子，问这个棋盘上的棋子是否为合法游戏过程中能够产生的棋子摆放状况，如果是返回true，否则返回false。
class Solution {
// visited数组保存当前棋子的摆放位置
char[][] visited = {{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '}};
// 方法gameStop()用于判断当前游戏是否已经结束
private boolean gameStop(){
for(int i = 0; i < 3; i++){
if(visited[i][0] != ' ' &&
visited[i][0] == visited[i][1] &&
visited[i][1] == visited[i][2])
return true;
}
for(int i = 0; i < 3; i++){
if(visited[0][i] != ' ' &&
visited[0][i] == visited[1][i] &&
visited[1][i] == visited[2][i])
return true;
}
if(visited[0][0] != ' ' &&
visited[0][0] == visited[1][1] &&
visited[1][1] == visited[2][2]){
return true;
}
if(visited[2][0] != ' ' &&
visited[2][0] == visited[1][1] &&
visited[1][1] == visited[0][2]){
return true;
}
return false;
}
// 递归函数的含义：三个参数分别为给定的初始化棋子状况的棋盘，当前步，总共需要的步数
// 按照给定的初始化棋子状况的棋盘，按照题目要求的下棋规则摆放棋子，能否得到初始化的棋子状况
// 由于要求第一步放X，第二步放O，并依次放置，因此奇数步放X，偶数步放O
// 注意井字游戏结束的规则，需要判断当前是否已经是结束游戏了
private boolean isValid(String[] board, int step, int totalStep){
// 得到题目初始化的棋盘状况，返回true
if(step == totalStep + 1)
return true;
// 还未完成题目初始化的棋盘状况，而且游戏已经结束，返回false
if(gameStop())
return false;
// 当前步是奇数步则放的棋子是X，偶数步放的棋子是O
char curStepType = step % 2 == 0 ? 'O' : 'X';
// 遍历初始化棋盘中的棋子，找到当前步需要摆放的一个可能的位置，递归 回溯寻找所有的可能
// visited数组记录当前位置是否已经放置过棋子 ' '为没有放置棋子
// 这个递归回溯的过程是一个DFS的过程
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(board[i].charAt(j) == curStepType && visited[i][j] == ' '){
visited[i][j] = curStepType;
if(isValid(board, step + 1, totalStep))
return true;
visited[i][j] = ' ';
}
}
}
return false;
}
public boolean validTicTacToe(String[] board) {
// 计算总步数
int totalStep = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(board[i].charAt(j) != ' ')
totalStep++;
}
}
return isValid(board, 1, totalStep);
}
}
2. 779. 第K个语法符号
-
可以按照题目的要求写出几行来看看，第一行是0，第二行是01，第三行通过第二行的0得到01、通过第二行的1得到10，因此这实际上是一个二叉树的结构，而且观察发现另外一个特点，如果一个节点是其父节点的左子节点，则其值与其父节点相同；如果是右子节点，则其值与其父节点不同；进一步描述，如果每一行的节点从1开始从左到右数，奇数位的节点和其父节点值相同，偶数位的不相同。因此如果需要得到某一行从左到右数第K个节点的值，只需要判断是偶数还是奇数位，然后通过其父节点的值得到该第K个节点的值。这是一个递归的过程。只有第一行的值是给出的是0，这样就能递归的解决某一行第K个的问题。
-
在一棵二叉树中，如果该节点是当前行的第K个，如果K是奇数，则其父节点在上一行中的位置是 (k + 1) / 2；如果k是偶数，则其父节点在上一行中的位置是 k / 2
-
方法：递归，递归函数的含义：对于传入的参数行数N和第K个，得到该第K个位置上的字符值；终止条件是当行数是N时返回0，递归问题的时间复杂度是最大调用栈的深度 * 每个调用的时间复杂度，这里每个调用的时间复杂度是常数，因此整体的时间复杂度就是最大调用栈的深度，即O(N)
class Solution {
public int kthGrammar(int N, int K) {
if(N == 1)
return 0;
if(K % 2 == 0)
return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
else
return kthGrammar(N - 1, (K + 1) / 2);
}
}
3. 698 划分为k个相等的子集
-
划分为k个非空子集，而且所有的子集和都相同，则通过计算出所有数值的和，然后除以k，得到每个子集和的大小target，如果target不是整数则直接返回false，否则题目可以改为划分成k个非空子集，每个子集和值都是target
-
方法：递归 回溯
-
未剪枝，提交超时
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num : nums)
sum += num;
if(sum % k != 0)
return false;
visited = new boolean[nums.length];
return canPartition(nums, k, sum / k, 0);
}
private boolean canPartition(int[] nums, int k, int target, int sum){
if(k == 1){
for(int i = 0; i < nums.length; i++)
if(!visited[i])
sum += nums[i];
return sum == target;
}
if(sum == target)
return canPartition(nums, k - 1, target, 0);
for(int i = 0; i < nums.length; i++){
if(visited[i])
continue;
visited[i] = true;
if(canPartition(nums, k, target, sum + nums[i]))
return true;
visited[i] = false;
}
return false;
}
private boolean[] visited;
}
- 剪枝后，提交通过，剪枝主要是对查找一个子数组其和为target时，要添加进子数组中的新元素应该在当前元素后面，前面的已经不需要再尝试了(再尝试就是重复判断，造成冗余)
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if((sum % k) != 0)
return false;
visited = new boolean[nums.length];
return canPartition(nums, k, sum / k, 0, 0);
}
boolean[] visited;
// 递归函数的含义：能否将传入的数组nums中未使用的值，划分成k个非空子数组，每个子数组的和都是target
// sum为当前正在划分的子数组的和，start为当前正在划分的子数组需要在nums中查找新元素的起始位置
private boolean canPartition(int[] nums, int k, int target, int sum, int start){
if(k == 1){
for(int i = 0; i < nums.length; i++){
if(!visited[i])
sum += nums[i];
}
return sum == target;
}
// 如果找到了一个和为target的子数组，则继续找下一个子数组，否则继续为当前子数组查找值使其和为target
if(saum == target)
return canPartition(nums, k - 1, target, 0, 0);
for(int i = start; i < nums.length; i++){
if(visited[i])
continue;
visited[i] = true;
if(canPartition(nums, k, target, sum + nums[i], i + 1))
return true;
visited[i] = false;
}
return false;
}
}
投递华为等公司10个岗位 >
