LeetCode Subtree of Another Tree Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

---

判断二叉树t是否是二叉树s的子树。如果t是s从node0开始的子树，则t必须和node0子树完全一样，node0不能有多余的孩子，比如样例2中node0的子树多有一个节点0，所以是False。 首先写一个子程序check判断子树s和t是否相等，然后在主程序中使用先序遍历s，如果发现s的某个节点node0的值和t的根节点相等，则可以进入check(node0,t)判断node0子树是否和t相等。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; queue<TreeNode*> q; q.push(s); while (!q.empty()) { TreeNode *tmp = q.front(); q.pop(); if (tmp->val == t->val) { if (check(tmp, t))return true; } if (tmp->left != NULL)q.push(tmp->left); if (tmp->right != NULL)q.push(tmp->right); } return false; } }; [/cpp] 本代码提交AC，用时29MS。 还有一种更简洁漂亮的解法。如果t是s的子树，有三种情况，t要么和s完全相等check(s,t)，要么等于s的某个左子树isSubtree(s->left,t)，要么等于s的某个右子树isSubtree(s->right,t)。所以主程序和子程序都可以递归。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; if (check(s, t))return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } }; [/cpp] 本代码提交AC，用时32MS。]]>

LeetCode Binary Tree Tilt Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0. The tilt of the whole tree is defined as the sum of all nodes’ tilt. Example:

Input:
         1
       /   \
      2     3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.
2. All the tilt values won’t exceed the range of 32-bit integer.

---

定义二叉树一个节点的tilt为其左子树元素之和与右子树元素之和的差的绝对值。整棵二叉树的tilt为所有节点的tilt之和。现在要求一棵二叉树的tilt。 简单题，递归求解元素之和，然后更新tilt。都是递归到叶子节点，然后累加和往父亲节点走。 代码如下： [cpp] class Solution { private: void dfs(TreeNode* root, int& sum, int& tilt){ if(root == NULL) { sum = 0; tilt = 0; } else { int lsum = 0, rsum = 0, ltilt = 0, rtilt = 0; dfs(root->left, lsum, ltilt); dfs(root->right, rsum, rtilt); sum = lsum + rsum + root->val; tilt = ltilt + rtilt + abs(lsum – rsum); } } public: int findTilt(TreeNode* root) { int sum = 0, tilt = 0; dfs(root, sum, tilt); return tilt; } }; [/cpp] 本代码提交AC，用时16MS。]]>

LeetCode Verify Preorder Serialization of a Binary Tree One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node. Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree. Each comma separated value in the string must be either an integer or a character '#' representing null pointer. You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3". Example 1: "9,3,4,#,#,1,#,#,2,#,6,#,#" Return true Example 2: "1,#" Return false Example 3: "9,#,#,1" Return false

---

根据树的先序遍历结果，在不重构树的情况下，判断该先序遍历是否合法。 解法1，使用栈。因为先序遍历的顺序是根左右，如果我们遇到序列x,#,#，其中x不是#时，说明x的左右孩子都是#，此时，我们将x,#,#替换为#，表示将以x为根的子树替换为一个#。如此循环，如果栈中最终只剩下一个#，说明该序列合法。 比如样例”9,3,4,#,#,1,#,#,2,#,6,#,#”：

• 9,3,4,#,# → 9,3,#
• 9,3,#,1,#,# → 9,3,#,# → 9,#
• 9,#,2,#,6,#,# → 9,#,2,#,# → 9,#,# → #

不需要担心遇到x,#,#,#的情况，因为在遍历到第二个#时，就符合x,#,#的pattern了，会把x,#,#变成#。 代码如下： [cpp] class Solution { public: bool isValidSerialization(string preorder) { stack<string> stk; int i = 0, j = 0, n = preorder.size(); while (j < n) { while (j < n&&preorder[j] != ‘,’)++j; string node = preorder.substr(i, j – i); if (node == "#") { while (!stk.empty() && stk.top() == "#") { stk.pop(); if (stk.empty())return false; stk.pop(); } } stk.push(node); i = ++j; } return stk.size() == 1 && stk.top() == "#"; } }; [/cpp] 本代码提交AC，用时6MS。 解法2，利用度的信息。一棵二叉树通过题目中的加#策略之后，变成了一棵满二叉树。这里的满是指一个节点要么有两个孩子，要么没有孩子，不存在有一个孩子的情况。（把#也看成孩子） 那么如果是叶子节点，则只贡献一个入度；如果是非叶子节点，则贡献一个入度和两个出度。所以diff=outdegree-indegree不可能是负数。 所以当来了一个节点，先–diff，因为这个节点肯定会贡献一个入度。然后判断这个节点如果是非叶子节点，则diff+=2，因为非叶子节点贡献两个出度。程序结束时，如果diff==0，则说明序列合法，否则不合法。因为就完整的树来说，入度肯定等于出度的，一条边对于父亲节点来说贡献出度，但对于孩子节点来说，贡献入度，所以总的入度和出度是相等的。 初始时，因为根节点没有入度，但是在外层while循环中，我们把根节点也看成普通的节点了。普通节点假设是有入度的，所以一进来就会–diff。所以初始时给根节点也补上一个入度，即diff=1，这样进入while之后，–diff不至于小于0。 代码如下： [cpp] class Solution { public: bool isValidSerialization(string preorder) { int i = 0, j = 0, n = preorder.size(), diff = 1; while (j < n) { while (j < n&&preorder[j] != ‘,’)++j; string node = preorder.substr(i, j – i); if (–diff < 0)return false; if (node != "#")diff += 2; i = ++j; } return diff == 0; } }; [/cpp] 本代码提交AC，用时3MS。 解法3，也是利用度的信息。前面说了，通过题目中的策略，一棵普通二叉树已经变成了一棵满二叉树，满二叉树的特点是叶子节点的数目=非叶子节点的数目+1。简单证明如下： 假设叶子节点数为leaves，非叶子节点数为nonleaves。则总节点数为leaves+nonleaves，总边数就是leaves+nonleaves-1。一条边贡献两个度，所以总度数就是2(leaves+nonleaves-1)。从另一个角度，一个叶子节点贡献一个度，一个非叶子节点贡献3个度，根节点也是非叶子节点，但它只贡献两个读，所以总度数加起来就是leaves+3*nonleaves-1。令2(leaves+nonleaves-1)=leaves+3*nonleaves-1，就解出了leaves=nonleaves+1。 因为先序遍历是根左右，所以我们找一个满足leaves=nonleaves+1的最短前缀，如果这确实是一个合法的序列，则这个最短前缀就应该是序列本身。因为一棵满二叉树，在遍历的过程中是不会满足leaves=nonleaves+1的，只有当整棵树都遍历完之后才会满足这个条件。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

上面这棵树，虽然在遍历到节点2时，如果不再往下遍历了，看起来也是满二叉树，但是2是有孩子的，所以会被判断为nonleaves，所以还是不满足leaves=nonleaves+1。 代码如下： [cpp] class Solution3 { public: bool isValidSerialization(string preorder) { int leaves = 0, nonleaves = 0; int i = 0, j = 0, n = preorder.size(); while (j < n) { while (j < n&&preorder[j] != ‘,’)++j; string node = preorder.substr(i, j – i); if (node == "#")++leaves; else ++nonleaves; i = ++j; if (leaves – nonleaves == 1 && j < n)return false; } return leaves – nonleaves == 1; } }; [/cpp] 本代码提交AC，用时6MS。]]>

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example:

Input:      1    / \   2   3  / \  / 4  5 6 Output: 6

---

计算完全二叉树的节点个数。如果忽略完全二叉树的性质，像普通二叉树那样进行遍历（先序、中序、后序都可以）统计节点个数，会TLE，所以还是需要用到完全二叉树的性质的。 这里的完全二叉树是指除了最后一层，其他层都是满的，并且最后一层所有节点都是靠左的。具体定义可以看维基百科，下图就是一个完全二叉树的例子： 如果二叉树是满的，比如下面这种，且树的高度是h，则树的节点个数等于$2^h-1$。 那么怎样判断一棵完全二叉树是否是满的呢，只需求一下其极左高度lh和极右高度rh是否相等，如果相等，则是满的，可以用上述公式求解节点数。如果不是满的，则在其左右子树中递归求解节点数，再加上根节点这个节点个数1。 代码如下：

class Solution {
public:
    int countNodes(TreeNode* root)
    {
        if (!root)
            return 0;
        int lh = 0, rh = 0;
        TreeNode *l = root, *r = root;
        while (l) {
            ++lh;
            l = l->left;
        }
        while (r) {
            ++rh;
            r = r->right;
        }
        if (lh == rh)
            return (1 << lh) – 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

本代码提交AC，用时82MS。
以上代码还可优化，因为如果知道父亲节点的高度时，其实也就知道了孩子节点的高度了，就是父亲的高度减1，所以在递归时，可以保留高度信息，减少冗余计算。代码如下：

class Solution {
private:
    int height(TreeNode* root, int lh, int rh)
    {
        if (lh == -1) {
            lh = 0;
            TreeNode* l = root;
            while (l) {
                ++lh;
                l = l->left;
            }
        }
        if (rh == -1) {
            rh = 0;
            TreeNode* r = root;
            while (r) {
                ++rh;
                r = r->right;
            }
        }
        if (lh == rh)
            return (1 << lh) – 1;
        return height(root->left, lh – 1, -1) + height(root->right, -1, rh – 1) + 1;
    }
public:
    int countNodes(TreeNode* root) { return height(root, -1, -1); }
};

本代码提交AC，用时55MS，快了一些。