【实战】关于树的性质相关变种题目

一、从二叉树的角度看递归

题解报告LeetCode#100：相同的树

题意：LeetCode#100：相同的树

思路：判断两棵树二叉树是否一样，这是典型的使用递归解决的问题。

代码：

class Solutio {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (q == null || p == null) {
            return false;
        }
        return q.val == p.val 
            && isSameTree(q.left, p.left) && isSameTree(q.right, p.right);
    }
}

题解报告LeetCode#101：判断二叉树是否左右对称

题意：LeetCode#101：对称二叉树

思路：

这道题我觉得掌握两种解法就可以了：（1）递归写法；（2）非递归写法：使用双端队列。

• 解法一：先拷贝一颗二叉树，再反转，将反转以后的二叉树和自己比较，看看是否相等，这个思路就转化成了以前我们解决过的问题。另外复制的时候，我们可以反着复制，然后比较；
• 解法二：设置一个辅助函数，递归去判断两颗子树是否镜面对称；
• 解法三：还可以使用辅助数据结构“双端队列”完成。使用队列，并且是双端队列（链表实现）这个辅助数据结构。画出出队入队的顺序，就很清楚了。

代码：

• 解法二：```java class Solution {

  public boolean isSymmetric(TreeNode root) {

    if (root == null) {
        return true;
    }
    return helper(root.left, root.right);
  

  }

  public boolean helper(TreeNode root1, TreeNode root2) {

    if (root1 == null && root2 == null) {
        return true;
    }
    if (root1 == null || root2 == null) {
        return false;
    }
    return root1.val == root2.val && 
        helper(root1.right, root2.left) && helper(root2.right, root1.left);
  

  }

}

- 解法三：```java
class Solution {

    public boolean isSymmetric(TreeNode root) {
        if (roo == null || (root.left == null && root.right == null)) {
            return true;
        }
        // 用队列保存节点
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 将根节点的左右孩子放到队列中
        queue.add(root.left);
        queue.add(root.right);
        while (queue.size() > 0) {
            // 从队列中取出两个节点，再比较这两个节点
            TreeNode left = queue.removeFirst();
            TreeNode right = queue.removeFirst();
            // 如果两个节点都为空就继续循环，两者有一个为空返回 false
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }
            // 将左节点的左孩子，右节点的右孩子放入队列
            queue.add(left.left);
            queue.add(right.right);
            // 将左节点的右孩子，右节点的左孩子放入队列
            queue.add(left.right);
            queue.add(right.left);
        }

        return true;
    }

}

题解报告LeetCode#110：平衡二叉树

题意：LeetCode#110：判断是否为平衡二叉树

思路：

严格按照定义，使用后序遍历计算每一个节点的度，因为要计算一个整数，所以递归函数应该设计成一个返回 int 的函数。

代码：

public class Solution {

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return helper(root) == -1;
    }

    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = helper(node.left);
        int right = helper(node.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.math(left, right) + 1;
    }

}

题解报告LeetCode#112：路径总和

题意：LeetCode#112：路径总和

思路：这道题想清楚递归关系，就能很简单的解答，直接看代码；

代码：

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null) {
            return true;
        }
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

题解报告LeetCode#113：路径总和Ⅱ

题意：LeetCode#113：路径总和Ⅱ

思路：思路基本上和上一题没差，不过这一题考察的主要是回溯思想，只是回溯树被具体化出来了，代码中有两处需要注意的地方。

代码：

class Solution {

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();    

        return getPathSumHelper(root, sum, res, path);
    }

    private List<List<Integer>> getPathSumHelper(TreeNode root, int sum,
                                                List<List<Integer>> res, LinkedList<Integer> path) {
        if (root == null) {
            return res;
        }

        sum -= root.val;
        path.addLast(root.val);
        if (sum == 0 && root.left == null && root.right == null) {
            // 这里必须新建一个，因为代码中的这个 path 的还会被其他分治引用
            res.add(new LinkedList<>(path));
        }
        getPathSumHelper(root.left, sum, res, path);
        getPathSumHelper(root.right, sum, res, path);

        // 这里必须移除，以避免对后序造成影响
        path.removeLast();
        return res;
    }
}

题解报告LeetCode#129：求根到叶子结点数字之和

题意：LeetCode#129：求根到叶子结点数字之和

思路：这道题基本上和 LeetCode#113 没啥差别

代码：

class Solution {

    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }

    private int helper(TreeNode root, int res) {
        if (root == null) {
            return 0;
        }
        int temp = res * 10 + root.val;
        // 到达根节点，递归终止
        if (root.left == null && root.right == null) {
            return temp;
        }
        return helper(root.right, temp) + helper(root.left, temp);
    }
}

题解报告LeetCode#257：二叉树的所有路径

题意：LeetCode#257：二叉树的所有路径

思路：二叉树的遍历，前序遍历

代码：

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }

    private void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {
                paths.add(pathSB.toString()); // 把答案加到路径中
            } else {
                pathSB.append("->"); // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            } 
        } 
    }
}

题解报告LeetCode#404：左叶子之和

题意：LeetCode#404：左叶子之和

思路：简答题，唯一需要注意的就是判断这个节点是否是左叶子的条件

代码：

class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        int res = 0;
        if (root == null) {
            return res;
        }

        if (root.left != null && root.left.left == null && root.left.right == null) {
            res += root.left.val;
        }

        res += sumOfLeftLeaves(root.left);
        res += sumOfLeftLeaves(root.right);

        return res;
    }

}

题解报告LeetCode#437：路径总和Ⅲ

题意：LeetCode#437：路径总和Ⅲ

思路：

• 思路一
• 思路二
  这道题还可以使用另外一个解法，“前缀和”。就是到达当前元素的路径上，之前所有元素的和。前缀和怎么应用呢？
  如果两个数的前缀总和是相同的，那么这些节点之间的元素总和为零。进一步扩展相同的想法，如果前缀总和 currSum，在节点 A 和 节点 B 处相差 target，则位于节点 A 和节点 B 之间的元素之和是 target。
  因为本题中的路径是一颗树，从根往任一节点的路径上（不走回头路），有且仅有一条路径，因为不存在环。（如果存在环，那么前缀和就不能使用了，需要改造算法）
  抵达当前节点（即 B 节点）后，将前缀和累加，然后查找在前缀和上，有没有前缀和 currSum - target 的节点（即 A 节点），存在即表示从 A 到 B 有一条路径之和满足条件的情况。如果加上满足前缀和 currSum - target 的节点的数量。然后递归进入左右子树。
  左右子树遍历完成之后，回到当前层，需要把当前节点添加的前缀和去除。避免回溯之后影响上一层。因为思想是前缀和，不属于前缀，我们就要去掉它。
  核心代码：java // 当前路径上的和 currSum += node.val; // currSum - target 相当于找路径的起点，起点的 sum + target = currSum，当前点到起点的记录就是 target res += prefixSumCount.getOrDefault(currSum - target, 0); // 更新路径上当前节点前缀和的个数 prefixSumCount.put(currSum, prefixSum.getOrDefault(currSum, 0) + 1);

代码：

• 思路一：```java class Solution { public int pathSum(TreeNode root, int sum) {

    if (root == null) {
        return 0;
    }
    return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
  

  }

  private int dfs(TreeNode root, int sum) {

    int res = 0;
    if (root == null) {
        return res;
    }
    if (root.val == sum) {
        res += 1;
    }
    res += dfs(root.left, sum - root.val);
    res += dfs(root.right, sum - root.val);
  
    return res;
  

  } } ```

• 思路二：```java class Solution { public int pathSum(TreeNode root, int sum) {

    // key 是前缀和，value是大小为 key 的前缀和出现的次数
    HashMap<Integer, Integer> prefixCountSum = new HashMap<>();
    // 前缀和为 0 的一条路径
    prefixCountSum.put(0, 1);
    // 前缀和的递归回溯思路
       return recursionPathSum(prefixCountSum, root, sum, 0);
  

  }

  /**

  • 前缀和的递归回溯思路
  • 从当前节点反推到根节点(反推比较好理解，正向其实也只有一条)，有且仅有一条路径，因为这是一棵树
  • 如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
  • 所以前缀和对于当前路径来说是唯一的，当前记录的前缀和，在回溯结束，回到本层时去除，保证其不影响其他分支的结果
  • @param node 树节点
  • @param prefixSumCount 前缀和Map
  • @param target 目标值
  • @param currSum 当前路径和

  • @return 满足题意的解 */ private int recursionPathSum(HashMap prefixCountSum, TreeNode root, int target, int curSum) { int res = 0; // 1. 递归终止条件 if (root == null) {

     return res;
    

    } // 2. 本层要做的事情 curSum += root.val; //—-核心代码 // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径 // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了 // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target res += prefixCountSum.getOrDefault(target - curSum, 0); // 更新路径上当前节点前缀和的个数 prefixCountSum.put(curSum, prefixCountSum.getOrDefault(curSum, 0) + 1);

    // 3. 进入下一层 res += recursionPathSum(prefixCountSum, root.left, target, curSum); res += recursionPathSum(prefixCountSum, root.right, target, curSum);

    // 4. 回到本层，恢复状态，去除当前节点的前缀和数量 prefixCountSum.put(curSum, prefixCountSum.get(curSum) - 1);

    return res; } } ```

二、二叉搜索树相关问题

题解报告LeetCode#1373：二叉搜索子树的最大键值和

题意：LeetCode#1373：二叉搜索子树【困难】

思路：这条题的思路其实很简单，主要有以下三步

1. 递归遍历一颗二叉树，判断递归中的结点的左右子树是否为二叉搜索树（BST）
2. 如果左子树是 BST，右子树也是 BST，那么就继续判断当前结点的值是否大于左子树的最大值，并且同时小于右子树的最小值。如果是则说明当前结点所代表的树也是 BST。
3. 只要第二点有一个条件不满足，该节点的所有祖先结点都不可能构成 BSF，其祖先结点所得到的最大键值和只能指靠另外一侧的子树结点了。

上述就是大致的思路过程了，但是我们还需要考虑用什么来存储代码过程中的值，例如当前结点的左右子树的最大值/最小值，当前二叉搜索树的键值和，这些才是真正考验数据结构能力的地方。下面轮到代码发言。

代码：

class Solution {

    // 静态内部类，用于保存树的所有节点值的和
    static class State {
        int val; // BST 子树的所有节点值的和
        int minElem = Integer.MIN_VALUE; // BST 子树的最小值
        int maxElem = Integer.MAX_VALUE; // BST 子树的最大值
        public State(int i) {
            val = i;
        }
    }

    private int maxSum;

    private int maxSumBST(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        State leftCnt = new State(0);
        if (isBST(root, leftCnt)) {
            maxSum = Math.max(maxSum, leftCnt.val);
        }
        return Math.max(maxSum, 0);
    }

    public boolean isBST(TreeNode root, State leftCnt) {
        if (root == null) {
            return true;
        }

        State leftCnt = new State(0);
        boolean leftFlag = isBST(root.left, leftCnt);
        boolean rightFlah = isBST(root.right, rightCnt);
        if (leftFlag && (root.left == null || leftCnt.maxElem < root.val)
           && rightFlag && (root.right == null || rightCnt.minElem > root.val)) {
            // 左子树是 BST，右子树是 BST；当前结点的值大于左子树的最大值并且小于右子树的最小值

            // 当前 State 未被更新，将最小值和最大值设为当前结点的值
            if (leftCnt.minElem == Integer.MIN_VALUE) {
                leftCnt.minElem = root.val;
            }
            if (leftCnt.maxElem == Integer.MAX_VALUE) {
                leftCnt.maxElem = root.val;
            }

            // 已知当前结点构成 BST，将左子树的状态和右子树的状态结合，用于表示当前结点的状态
            // 故将左状态的最大值赋值为右子树状态的最大值
            // 如果右子树为空，则将左状态的最大值设为当前值
            if (rootr.right != null) {
                leftCnt.maxElem = rightCnt.maxElem;
            } else {
                leftCnt.maxElem = root.val;
            }

            leftCnt.val    += root.val + rightCnt.val;
            maxSum = Math.max(maxSum, leftCnt.val);

            return true;
        } else {
            // 当前结点不能构成 BST，则分别检查左子树和右子树是否构成 BST
            // 如果构成，则分别计算和的最大值
            if (leftFlag) maxSum = Math.max(maxSum, leftCnt.val);
            if (rightFlag) maxSum = Math.max(maxSum, rightCnt.val);
            return false;
        }
    }

}

三、完全二叉树相关问题

题解报告LeetCode#222：完全二叉树的节点个数

题意：LeetCode#222：完全二叉树的节点个数

思路：

• 方法一：线性时间
  最简单的方法就是用递归一个一个的计算节点
• 方法二：二分搜索
  方法一并没有利用完全二叉树的特性。完全二叉树中，除了最后一层外，其余每层节点都是满的，并且最后一层的节点全部靠向左边。
  再来回顾一个满二叉的节点个数怎么计算，如果满二叉树的层数为 h，则总结点树为：2^h - 1。
  那么我们来对 root 节点的左右子树进行高度统计，分别记为 left 和 right，有以下两种结果：
  1. left == right。这说明，左子树一定是满二叉树，因为叶节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是 2^left - 1，加上当前这个 root 节点，则正好是 2^left。再对右子树进行递归统计。
  2. left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点 +root 节点，总数为 2^right。再对左子树进行递归查找。

关于如何计算二叉树的层数，可以利用下面的递归来计算，当然对于完全二叉树，可以利用其特点，不用递归直接算。

private int countLevel(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(countLevel(root.left), countLevel(root.right)) + 1;
}

如何计算 2^left，最快的方法就是移位计算，因为运算符的优先级问题，记得加上括号。

代码：

• 方法一```java public int countNodes(TreeNode root) { if (root == null){

    return 0;
  

  } return countNodes(root.left) + countNodes(root.right) + 1; } ```

• 方法二```java class Solution {

  private int countNodes(TreeNode root) {

    if (root == null) {
        return 0;
    }
  
    int left = countLevel(root.left);
    int right = countLevel(root.right);
    if (left == right) {
          return countLevel(root.right) + (1 << left);
    } else {
        return countLevel(root.left) + (1 << right);
    }
  

  }

  private int countLevel(TreeNode root) {

    int level = 0;
    while (root != null) {
        level += 1;
        root = root.left;
    }
    return level;
  

  } } ```