发布于

LeetCode-100-Same Tree及572-Subtree of Another Tree

之所以把这两道题放到一起，是因为第一道题的算法是第二道题的一块小零件，如果理解第一题的解法的话，那么看到第二题应该就很快有思路了。

Same Tree

本题的要求是判断两棵树是否相同。根据题目描述，两棵树相同的条件是这两棵树的结构相同，并且对应位置上的节点的值也相同。
我们将这两棵树分别称为 s和 t。首先先处理一些特殊的情况：

  • 当 s 和 t 中有一个不为空，也就意味着这两棵树的结构不同，因此应该返回 false。
  • 当 s 和t 全为空时，应该返回 true。
  • 当 s 和 t 全不为空时，此时先比较 s 和 t 的值是否相同，如果不同，则返回false, 如果相同，则递归地比较s 和 t 的左右孩子是否相同。

顺着以上思路，不难写出如下代码：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        if (p == NULL || q == NULL) {
            return false;
        }
        if (p->val != q->val) {
            return false;
        }
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

Subtree of Another Tree

本题的要求是判断 t 是否是 s 的子树，也就是说如果 t 和 s 的某一部分的结构和对应节点的值相同的话，那么 t 就是 s 的一棵子树。经过思考我们发现，其实这道题的核心思路就是判断 t 和 s 的某一部分是否是相同的，因此可以借用上面的算法。因此这个题的思路就很明了了：首先判断 s和 t 是否相同，相同则返回 true；否则判断 t 是否是 s 的左孩子或右孩子的子树。代码如下：

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if ( s == NULL) {
            return false;
        }
        if (isSameTree(s,t)) {
            return true;
        }
        return isSubtree(s->left,t) || isSubtree(s->right,t);
    }

private:
    bool isSameTree(TreeNode *s, TreeNode *t) {
        if (!s && !t) {
            return true;
        }
        if (s == NULL || t == NULL) {
            return false;
        }
        if (s->val != t->val) {
            return false;
        } else {
            return isSameTree(s->left,t->left) && isSameTree(s->right,t->right);
        }
    }
};
发布于

调试 LeetCode 上的二叉树相关题目的代码模板

在 LeetCode 上刷题时，只需要提供一个可以完成功能的函数就行了，但是这给我们的调试带来了不便。如果在出错时我们可以在本地 IDE 上调试我们的代码，那么就可以快速定位出问题所在。以下是一份可以用来直接运行的代码模板，针对的是LeetCode 上树这部分的题目。 继续阅读“调试 LeetCode 上的二叉树相关题目的代码模板”

发布于

递归在二叉树相关题目中的应用

最近集中刷了几道和二叉树有关的题目。由于二叉树本身就是递归定义的，因此使用递归算法解决二叉树的相关问题，不仅思路清晰，算法简单，而且代码量也比非递归的解法要小很多。在此将这些题目一并总结和记录一下。在介绍一般性的做法之前，先说一下自己总结出的经验。
经验一：使用一个辅助函数，在这个辅助函数中进行递归的操作，可以使代码变得更加简单。
经验二：在递归函数的开始处先处理特殊情况，也就是所谓的递归返回点。

下面是本文中二叉树的数据结构定义:

  • 合并两个二叉树，LeetCode-617-Merge Two Binary Trees。给出两个二叉树，将这个二叉树合并成一个新的二叉树。合并规则是对应位置上的值相加。最后返回新的二叉树的根节点。
    思路: 使用递归算法，在合并当前节点之前，先合并当前节点的左孩子和右孩子。

  • 前中后各种遍历。使用递归算法时这三种遍历的思路都是一样的，区别只是访问root节点的顺序。另外这几种遍历方法也可以使用非递归的方式实现，不过需要借助栈、队列等额外的数据结构，详见我的另一篇博客。

  1. 前序遍历

  2. 中序遍历

  3. 后序遍历

  • 判断两个二叉树是否是相同的，LeetCode-100-Same Tree。 两个二叉树相同的定义是这两个二叉树的结构相同，并且对应位置上的节点的数值也相同。

  • 判断一棵二叉树是否是对称的，LeetCode-101-Symmetric Tree。

  • 将一棵二叉树展平成一个单链表，Flatten Binary Tree to Linked List。

  • 判断一棵树上是否存在一条路径，使得该路径上的所有节点的值的和等于给定的数字，LeetCode-112-Path Sum。

  • 和上道题非常类似，但是要求求出所有的符合条件的路径，LeetCode-437-Path Sum II。

  • 修剪一棵二叉搜索树，LeetCode-669-Trim a Binary Search Tree。题干明确说明了该树是一棵二叉搜索树，所以具有如下的性质：某个节点的左子树上的每个节点的值都比该节点值小，而右子树上的每个节点的值都比该节点值大。因此，如果判断出当前节点的值在[L,R]之间，那么该节点就是一个子树的根节点；如果当前节点的值大于 R，那么根节点需要从它的左子树中寻找；如果当前节点的值小于 L，那么根节点需要从它的右子树中寻找。

  • 求一棵二叉树的最大深度，LeetCode-104-Maximum Depth of Binary Tree。

  • 求一棵二叉树的最小深度，LeetCode-111-Minimum Depth of Binary Tree。
    思路与上一题类似，不过要注意的是如果一个节点的左孩子或者右孩子为空的话，那么以这个节点为根节点的子树的 minDepth 为它的左孩子或右孩子的 minDepth。

  • 翻转一棵二叉树，LeetCode-226-Invert Binary Tree。

  • 将一棵二叉搜索树变为一棵大树，LeetCode-538-Convert BST to Greater Tree。也就是将一个节点的值更新为所有值大于该节点的节点的值之和。

  • 求一棵二叉树所有左叶子节点的数值之和，LeetCode-404-Sum of Left Leaves。

  • 对一棵二叉树进行层序遍历，LeetCode-102-Binary Tree Level Order Traversal。

  • 求一棵二叉树的根节点到各个叶子节点的路径表示的值的和，LeetCode-129-Sum Root to Leaf Numbers。