LeetCode-101-Symmetric Tree

这道题的题意是判断一棵二叉树是不是对称的,如下图,当一棵树呈现这样的结构时,就可以称作是对称二叉树。

Symetric Tree

我采用的是递归的方法,根据题意,如果输入的根节点为空的话,那么直接返回 true;否则调用一个辅助函数来处理根节点的左右子树。在这个辅助函数里面,我们将左右子树作为参数传入,先判断左右子树的结构是否相同,相同的前提下判断这两个镜像位置的节点的数值是否相同,然后递归调用。

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

今天刷剑指 offer,发现这道题还有另一种解法:首先定义另一种前序遍历A,也就是访问过父节点后,先遍历右子节点再遍历左子节点。那么一棵对称二叉树的A遍历和它的正常前序遍历结果是一样的。根据这种思路,可以写出如下的算法:

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        return isSymmetrical(root,root);
    }    
    bool isSymmetrical(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 isSymmetrical(root1->left, root2->right) && isSymmetrical(root1->right, root2->left);
    }
};

LeetCode-191-Number of 1 Bits

这道题是一道很有意思的题目,题意是求一个uint32_t 类型数字的二进制表示中字符1的个数。如数字11,它的二进制表示是00000000000000000000000000001011,因此1的个数是3。

当说到二进制表示时,我们可能首先就会想到这道题可以用位运算来解决。只要把输入的每一位依次拿出来和1做与运算,如果结果为1,则说明该位上的数字为1,否则为0。所以可以很快写出下面的解法:

class Solution {
public:
    int hammingWeight(uint32_t num) {
        int count = 0;
        while (num) {
            if (num & 1) {
                count++;
            }
            n >> 1;
        }
        return count;
    }
};

那么当输入不是无符号整数,而是有符号数时,上面的解法还适用嘛?
我们知道,当右移一个无符号整数时,会用0来填补左边的空位,因此上述解法的判断可以正常退出,但是当右移的是一个有符号数时,如果它是一个正数,则会用0来填补左边空位;如果是一个负数,则会用符号位也就是1来填补左边的空位,因此最后该数字会变成0xFFFFFFFF,从而陷入无限循环中。

我们可以换个思路,不让数字右移,而是将掩码位左移。

class Solution {
public:
    int hammingWeight(uint32_t num) {
        int mask = 1;
        int count = 0;
        while(mask) {
            if (num & mask) {
                count ++;
            }
            mask << 1;
        }
        return count;
    }
};

当左移时,将会在右侧补上0,因此如果掩码左移了32位,那么它将会变成0,所以循环就可以退出了。

这还不算完,在这道题的讨论区里,还有人提了这样一个解法:当该数不为0时,将该数减去1,所得的结果再和原数做与运算,然后再赋值给这个数,这样循环进行,直到退出。

class Solution {
public:
    int hammingWeight(uint32_t num) {
        int count = 0;
        while(num) {
            num = num & (num-1);
        }
        return count;
    }
};

至于原理,可以用下面👇这张图来解释:

191_Number_Of_Bits

我觉得一般能发现第一个方法中的不足,从而写出第二个算法的人已经是很厉害了,而第三个方法则显得有些 tricky,因此想不到也是很正常的,不过从中还是能够体会出位运算的神奇之处。

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);
        }
    }
};

树-前中后序遍历的非递归实现

前、中、后序遍历是对树进行的基础操作,当使用递归来实现时代码非常简单。但是由于递归时会不断将当前状态保存下来,因此在这些状态之间进行切换也非常耗费时间。下面就介绍一下用非递归的方式如何来实现这些操作。另外在本文最后还介绍了一下层序遍历。

Binary Tree Travel

二叉树的数据结构定义如下:

  • 前序遍历:非递归遍历通过栈来实现,并且有两种不同的实现方式。思路一是先将根节点压入栈,然后当栈不为空的时候,先将栈顶元素出栈并访问这个节点,然后依次将该节点的右孩子左孩子入栈。代码如下:

思路二则是使用回溯,先遍历完左子树,然后回溯遍历右子树。

  • 中序遍历:和前序遍历的实现非常类似,只不过访问节点的时机不同。

  • 后序遍历:后序遍历是这几种遍历方式中比较麻烦的一种。前面的算法的规律是,当一个节点的左子树已经访问完了后,会将当前节点从栈中直接弹出并访问这个节点,然后再遍历它的右子树。但是后序遍历时,当访问完一个节点的左子树后,先得从栈顶获得这个节点,得到它的右子树并访问右子树,当右子树访问之后,再从栈顶获得这个节点,然后去访问这个节点自身,然后将该节点出栈。可以看出,访问该节点的过程发生了两次,但是只有访问了它的右子树后才可以将这个节点从栈中弹出。因此我们需要标记该节点是否被访问过。代码如下:

  • 层序遍历:作为树的遍历方式的一种,虽然不如前面三种方式常见,但是也是非常有必要了解的。与前面三种方式不同的是,层序遍历使用了队列而不是栈这种结构。思路是:先将根节点入队,当队列不为空的时候,从队列头出队一个元素并访问它,然后将它的左右孩子依次入队。

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

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

下面是二叉树的通用数据结构:

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

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

  1. 前序遍历

  2. 中序遍历

  3. 后序遍历

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

  • 判断一棵二叉树是否是对称的,Symmetric Tree

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

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

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

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

  • 求一棵二叉树的最大深度,Maximum Depth of Binary Tree

  • 翻转一棵二叉树,Invert Binary Tree

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

  • 求一棵二叉树所有左叶子节点的数值之和,Sum of Left Leaves

LeetCode-21-Merge Two Sorted Lists

这道题的要求是合并两个有序单链表。描述很简单,思路更加简单,就是先创建一个新的链表节点,然后用两个指针指向这两个单链表,比较这两个指针指向元素的大小,将较小的一个的值赋给新节点的元素,如果这两个元素相同,那随便赋谁的值都可以。当这两个链表有一个已经遍历完之后,就直接把另一条链表的其余元素复制到新链表中去。
代码如下:

Update: 今天从剑指 offer 上看到了这道题的递归解法,相比于上面的方法,递归解法显得更加优美简单。代码如下:

LeetCode-9-Palindrome Number

这道题的题目是:判断一个数字是否是回文数,但是要求不能分配额外的空间。
思路很容易,就是看这个数字的前半部分和后半部分翻转后的值是否相同。我们可以利用取一个数字的各位上的数字的方法求出这个数字的后半部分翻转后的值:

注意,当x的位数是偶数时,直接比较res和x的值是否相同即可;但是当x的位数是奇数,如x=12321,当res=123、x=12,此时循环跳出,判断条件只要改成x==res%10即可。因此完整的代码是:

由这道题还可以引申出一道类似的题目:判断一个字符串是不是一个回文串。回文串的定义和回文数字类似,就是正着读倒着读效果是一样的字符串,如"charahc"。只需要用两个指针分别指向字符串的头和尾,比较当前这两个指针所指向的字符是否相同,若相同则继续移动这两个指针,直到这两个指针相遇为止。代码如下:

LeetCode-7-Reverse Integer

这道题仍然属于一道简单题。题目描述是这样的:给定一个32位signed int类型的整数,将它进行反转,如输入123返回321,输入-123返回-321。另外,题目下的提示中也说明了一些特殊情况,一种是输入10、100这样末尾是0的数字时应该返回什么,另外一种是反转1000000003 时,结果有可能溢出。

首先我们先来思考一下为什么上面的结果会溢出。输入整数的类型为signed int,因此用二进制形式表示时,第一位是一个符号位,剩下的31位用来表示数字。231 = 2147483648,所以输入数字的范围是-2147483648 ~ 2147483647。而1000000003反转的结果是3000000001,超出了上述范围,因此发生了溢出,此时直接返回0即可。代码如下: