Tree

总结类型：

• 完全子树（#222）
• BST（左右子树值的性质，注意不仅要满足parent-child relation，还要满足ancestor-grandchild relation，可以通过传入small/large变量，或者通过右节点的最左节点和左节点的最右节点来判断）（#333）
• Inorder（sorted）, preorder（[root][small][large]）, postorder traversal（recursively & iteratively）
• Height: The number of edges from the node to the deepest leaf. So the leaf node has height 0（#366，#572）
• Depth: The depth of a node is the number of edges from the node to the tree's root node. The root node has depth 0.
• stack & queue -> in preorder

Algorithm Crush

• Morris Traversal (change pointer, link the rightmost node of the left node to the root. we can apply this pattern to some other problems.)

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

这道题的一个难度其实在于要考虑负数。如果不用考虑负数，那么递归很好写。如果有了负数，那么对根，左孩子，右孩子有这么几种情况：

• 根
• 左孩子
• 右孩子
• 根和左孩子
• 根和右孩子
• 根和左孩子和右孩子

最大路径值不外乎这些情况。
在递归中，我们算完了这一层的最大值，要返回给上一层当左/右孩子时，因为必须与上一层无缝对接，就必须返回这几种情况中的一种：

• 根
• 根和左孩子
• 根和右孩子

对比当前层和上一层，两者的关系是：这一层返回的情况会成为下一层的左孩子或者右孩子。也就是说，我们这一层对根，左孩子，右孩子的讨论可以简化成下面这三种情况：

• 左孩子
• 右孩子
• 根和左孩子和右孩子

因为max（根，根和左孩子，根和右孩子）会返回到上一层变为上一层的左孩子/右孩子跟另一个子树去讨论，就是说这一层和上一层其实讨论了六种情况。

当然，我们要用一个全局变量来记录全局最大值。当根返回的时候，我们要比多一次全局变量以及返回值。在具体写code时，对于叶来说，要考虑到如何处理nullptr所代表的值。我这里先用INT_MIN表示了，设置了两个flag来进行0和INT_MIN之间的转换。

class Solution {
private:
    int gl_max = INT_MIN;
    int helper(TreeNode* root)
    {
        if (!root) return INT_MIN;
        int left = helper(root->left);
        int right = helper(root->right);
        bool left_null = false;
        bool right_null = false;
        if (left == INT_MIN) { left_null = true; left = 0; }
        if (right == INT_MIN) { right_null = true; right = 0; }
        gl_max = max(gl_max, max(root->val + left + right, max(left_null ? INT_MIN : left, right_null ? INT_MIN : right)));
        return max(root->val, max(root->val + left, root->val + right));
    }
    
public:
    int maxPathSum(TreeNode* root) 
    {
        return max(gl_max, helper(root));
    }
};

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

这道题用binary search就可以做了，我比较想让自己记住的一点是binary search的终止条件和start、end值，因为有时候会搞混：

• start = 0
• end = size
• mid = (start + end) / 2
• end condition: start == end

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

这道题真的是醉了~想了挺久的但想出的方法巨繁琐，一看评论区发现大神不愧是大神TAT

Recursion有时候真的可以很巧妙！！

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
    if (!root || root == p || root == q) return root; 
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    // 如果左右子树都是nullptr，就return nullptr
    // 如果左子树是null，右子树不是，就return左子树的值
    // 如果右子树是null，左子树不是，就return右子树的值
    // 如果左右子树都不是null，就return root
    return !left ? right : !right ? left : root;
}

大神的思路翻译一下的话就是：如果当前根的左右子树都包含着p或者q，那就说明当前根才是ancestor；如果当前根的左右子树都不包含p或者q，那就以null来说明不包括；如果当前根只有左或者右子树包含p或者q，那ancestor就是那个左或者右子树的根。理解容易，难以想出来啊~

我自己想思路的时候用了非常多的假设和条件，看到这么简洁的思路真是惊呆了。我想自己还是思路犯了根本性的错误，钻进死胡同里去了。。。

222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.
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 2h
nodes inclusive at the last level h.

做到这题感觉树它就是recursion，recursion它就是树。完全树的题目没怎么碰到过，这次知道了它方便利用的一些性质：

• 对于一个完全子树，高度多一，则子树节点个数翻倍
• 对于一个完全子树，它的高度由左子树外叶节点的深度决定

具体将这个性质应用到题目中来：

• 如果当前根的左子树和右子树的高度一致，那么说明，至少左子树是完全的。我们可以用1<<h的方法，来算出左子树的节点个数，对于右子树，进行recursion的操作。
• 如果当前根的左子树和右子树的高度不是一致的，右子树是完全的。我们也可以进行同样的方法算出右子树的节点个数，对左子树进行recursion操作。只不过这个情况和上一点的情况相比，h的高度要-1。

时间复杂度上，我们每次找深度用了logn的时间，最坏情况下要找logn次（比如该树离完全树只有一个node之差）。所以时间复杂度是O（(logn)^2）。

class Solution {
private:
    int height(TreeNode* root, int h)
    {
        if (!root) return h;
        return height(root->left, h + 1);
    }
    
public:
    int countNodes(TreeNode* root) 
    {
        if (!root) return 0;
        int left_h = height(root->left, 0);
        int right_h = height(root->right, 0);
        if (left_h == right_h) return (1 << left_h) + countNodes(root->right);
        else return (1 << right_h) + countNodes(root->left);
    }
};

114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

我在思考这个问题的时候，想，如果要把左子树变到右子树去，那么右子树的信息不是要丢失吗？这么一来就要把左右子树交换，这么一来还不如先翻转树来得方便。于是我用递归的方式做了，方法是先翻转树，然后再用先序遍历。

其实用迭代的方式也可以做。当我们将左右子树连起来的时候，右子树消失是没有关系的，因为可以用左子树得到嘛。这与morris traversal有异曲同工之妙，看来让我们改变树的结构的时候，经常可以用得到这一招。

那怎么去连呢？扁平化后的树显然是先序遍历的结果。先序遍历是深度搜索中的一种，也就是说先将左子树先搜索完再搜索右子树。所以我们可以将右子树连在左子树的最后一个节点，也就是左节点的最右节点。

class Solution {
public:
    void flatten(TreeNode* root) 
    {
        while (root)
        {
            while (root->left)
            {
                TreeNode* left = root->left;
                while (left->right) left = left->right;
                left->right = root->right;
                root->right = root->left;
                root->left = nullptr;
                root = root->right;
            }
            root = root->right;
        }
    }
};

366. Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

这道题的insight在于发现，所有的叶节点的高度都一致。高度的定义是，从该节点到外叶节点经过的边数量。我们只要把所有高度为H的节点放进vector[H]中，就是结果。

class Solution {
private:
    vector<vector<int>> res; 
    int helper(TreeNode* root)
    {
        if (!root) return -1;
        int height = 1 + max(helper(root->left), helper(root->right));
        if (res.size() == height) res.push_back({});
        res[height].push_back(root->val);
        return height;
    }
    
public:
    vector<vector<int>> findLeaves(TreeNode* root) 
    {
        helper(root);
        return res;
    }
};

654. Maximum Binary Tree

这题O(n^2)的方法就不去想了吧，可以做到更好的O(n)：

1、假如当前数比上一个数小，就把当前树做成上一个树的右子树。这很明显，因为右子树总是递减的。

2、关键当当前数比前面一个数大的时候，我们要寻找第一个比当前数大的树T，让T右子树等于当前树，当前树的左子树等于T的原右子树。我们要保证的是，对于当前数，它能将T以后，和当前数以前的这些数，作为当前树的左子树。这个idea不难发现，但是在写code的时候，我自己写的work but too compliated，因为我们的关注点很大程度上在于“上一个”数，我们可以采用stack的思想。感谢评论区的帮助。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
    {
        if (nums.empty()) return nullptr;
        vector<TreeNode*> stk;
        for (int num: nums)
        {
            TreeNode* cur = new TreeNode(num);
            while (stk.size() && stk.back()->val < num)
            {
                cur->left = stk.back();
                stk.pop_back();
            }
            if (stk.size())
            {
                stk.back()->right = cur;
            }
            stk.push_back(cur);
        }
        return stk.front();
    }
};

我自己写code的时候把上述两种情况分开讨论，写的比较长，但是这个方法说明，我们遇到（2）情况的时候，其实是先遇到了（2）情况，然后因为pop掉了一些数，所以又会回到（1）情况去了。这样的code更加精炼。

538. Convert BST to Greater Tree

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

分析清楚就很好做！可惜我太快开始写了，直到重新理思路才发现很简单。

我们从最大的节点开始更新，以从大到小的顺序来中序遍历这棵树。

• 右节点是空指针的时候，当前节点 += 比它大的节点和（需要传入一个变量sum来记录）
• 右节点非空的时候，当前节点 += 比它大的节点和（由递归返回）
• 左节点空的时候，返回sum
• 左节点非空的时候，先遍历左节点再返回，传入变量sum为当前节点的值

class Solution {
private:
    int helper(TreeNode* root, int right_sum)
    {
        if (!root) return right_sum;
        root->val += helper(root->right, right_sum);
        return helper(root->left, root->val);
    }
    
public:
    TreeNode* convertBST(TreeNode* root) 
    {
        if (!root) return nullptr;
        helper(root, 0);
        return root;
    }
};

637. Average of Levels in Binary Tree

这道题不难，主要是想比较一下dfs和bfs做这道题的这两种方法。

1、DFS：用两个array来存放此层的总和和节点数量，用height来储存是第几层。

class Solution {
private:
    vector<double> sum;
    vector<int> count;
    vector<double> res;
    
    void dfs(TreeNode* root, int height)
    {
        if (!root) return;
        if (sum.size() == height)
        {
            sum.push_back(root->val);
            count.push_back(1);
        }
        else
        {
            sum[height] += root->val;
            count[height]++;
        }
        dfs(root->left, height + 1);
        dfs(root->right, height + 1);
    }
    
public:
    vector<double> averageOfLevels(TreeNode* root) 
    {
        dfs(root, 0);
        for (int i = 0; i < sum.size(); ++i)
        {
            res.push_back(sum[i] / count[i]);
        }
        return res;
    }
};

2、BFS：标准bfs方法。

class Solution {
private:
    vector<double> res;
    
public:
    vector<double> averageOfLevels(TreeNode* root) 
    {
        if (!root) return {};
        queue<TreeNode*> q;
        q.push(root);        
        while (q.size())
        {
            double sum = 0;
            double count = 0;
            queue<TreeNode*> q_next;
            while (true)
            {
                TreeNode* top = q.front();
                q.pop();
                if (top->left) q_next.push(top->left);
                if (top->right) q_next.push(top->right);
                sum += top->val;
                count++;
                if (q.empty()) { res.push_back(sum / count); break; }
            }
            q = q_next;
        }
        return res;
    }
};

285. Inorder Successor in BST

这道题可以不利用BST的性质，用inorder traversal来做。利用BST性质来做是我更喜欢的。要找到一个数的inorder successor，也就是找到比这个节点大，但又大得最少的数。我们可以从根出发：

1、如果我们发现当前节点的数比所要找节点p的数大的话，它是一个潜在的中序后续节点，把当前节点往左挪
2、如果当前节点比所要找的节点p的数小的话，无需更新中序后续节点，把当前节点往右挪
3、如果当前节点等于索要找的节点p的数的话，无需更新中序后续节点，把当前节点往右挪
4、如果当前节点是空指针的话，说明寻找结束了

可以想三种情况：

• p为左外叶节点，那么后续节点应该是它的parent。满足了第三个条件，由于触发了第四个条件，我们可以返回它的parent
• p的后续节点在其右子树的最左子树。此时第三个条件满足后，我们把当前节点往右挪，会一直触发第一个条件，直到我们找到右子树的最左子树
• p是某右子树外叶，它后续节点在ancestor上

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) 
    {
        TreeNode* res = nullptr;
        if (!p) return res;
        while (root)
        {
            if (root->val > p->val)
            {
                res = root;
                root = root->left;
            }
            else root = root->right;
        }
        return res;
    }
};

BST的题目肯定可以利用它的性质做的，以后尽量优先考虑用它的性质来做。我觉得这是一道简单但犀利的题目。

572. 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.

比较喜欢这道题是因为又可以利用height来避免讨论一些情况。

class Solution {
private:
    vector<TreeNode*> nodes;
    int get_h(TreeNode* n)
    {
        if (!n) return -1;
        return max(get_h(n->left), get_h(n->right)) + 1;
    }
    
    int find_nodes(TreeNode* s, int h)
    {
        if (!s) return -1;
        int height = max(find_nodes(s->left, h), find_nodes(s->right, h)) + 1;
        if (height == h) nodes.push_back(s);
        return height;
    }
    
    bool isSubtreeHelper(TreeNode* root1, TreeNode* root2)
    {
        if (!root1 && !root2) return true;
        if (root1 && !root2 || !root1 && root2) return false;
        if (root1->val != root2->val) return false;
        return isSubtreeHelper(root1->left, root2->left) && 
               isSubtreeHelper(root1->right, root2->right);
    }
    
public:
    bool isSubtree(TreeNode* s, TreeNode* t) 
    {
        int t_h = get_h(t);
        find_nodes(s, t_h);
        for (auto n: nodes)
        {
            if (isSubtreeHelper(n, t)) return true;
        }
        return false;
    }
};

449. Serialize and Deserialize BST

这道题利用preorder在BST中的性质。之前常做的是BST的中序遍历，结果是一个排序好的递增数列。而前序遍历的结果是，数列的结果会像这样：root(small)(large)，因为我们遍历的顺序是先根，再左子树，最后右子树。利用这个性质，我们可以在serialize的步骤，做一次前序遍历，而在deserialize的步骤，利用一个container来分割当前根的左右子树，根据是将数与根的值做比较。

时间上来说，与merge sort的思想类似：每一层找左右子树的时候都要用到O（n）的时候，树深logN层，最坏情况N层，所以O(n^2)的复杂度。

我尝试了用vector来implement this idea, but holy shit, C++竟然没有在未排序数列中找到第一个比目标值更大数这样的helper function，一口老血。最近觉得C++越来越不方便了。

class Codec {
private:
    string s;
    void dfs(TreeNode* root)
    {
        if (!root) return;
        s += to_string(root->val);
        s += ',';
        dfs(root->left);
        dfs(root->right);
    }
    
    queue<int> parse_int(string data)
    {
        queue<int> q;
        istringstream ss(data);
        string s;
        while (getline(ss, s, ',')) q.push(atoi(s.c_str()));
        return q;
    }
    
    TreeNode* construct_tree(queue<int> &q)
    {
        if (q.empty()) return nullptr;
        queue<int> left;
        TreeNode* root = new TreeNode(q.front());
        q.pop();
        while (q.size() && q.front() <= root->val)
        {
            left.push(q.front());
            q.pop();
        }
        root->left = construct_tree(left);
        root->right = construct_tree(q);
        return root;
    }
    
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        dfs(root);
        if (s.size()) s.pop_back();
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        queue<int> q = parse_int(data);
        return construct_tree(q);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

255. Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree. You may assume each number in the sequence is unique.

挺好的题，又是BST的前序序列的规律。可以用recursion做，也可以用一个stack做（本质上都是深搜嘛）。当前数如果比stack上最后一个数小的话，我们继续push上stack，等于还是在左子树。如果比stack上最后一个数大的话（按题意不考虑duplicate），说明我们到某个子树的右子树了。我们要找是哪个子树的右子树，就一直pop stack，一直到stack空了或者stack的数K大于当前数了，我们知道K之前被pop的那个数K_PREV其实就是树根。由于前序数列按照中、左、右的顺序遍历，而我们已经处理好了中和左，右子树的所有数都要比K_PREV大。所以记住K_PREV，再做同样的遍历，一直到数列最后。

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) 
    {
        stack<int> s;
        int low = INT_MIN;
        for (int num: preorder)
        {
            if (low > num) return false;
            while (s.size() && num > s.top()) 
            {
                low = s.top();
                s.pop();
            }
            s.push(num);
        }
        return true;
    }
};

549. Binary Tree Longest Consecutive Sequence II

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

我一开始想的思路：最大值无非三种情况

• 根 + 左树连续值（根与左树差1，并且记下与左树是递增还是递减关系）
• 根 + 右树连续值（根与右树差1，并且记下与右树是递增还是递减关系）
• 根 + 左树连续值 + 右树连续值（根与左右树都差一，并且左右树根值不同）

总体思路是对的，但是讨论的情况有点偏复杂。我用一个Result struct来记录当前节点究竟是递增还是递减的情况的话，对于左右树的递增/递减，我都只要选取最大的来作为当前节点的递增/递减，并返回这个结果。而对于第三种情况，我们其实无需再比较根是否与左右树都差一，并且左右树根值不同——当前节点的（递增+递减-1）就是可能是最大值情况。为什么呢？

• 递增和递减值肯定是从左和右两个不同的子树上得来，如果说满足了（根与左右树都差一，并且左右树根值不同）这个条件，（递增 + 递减 - 1）就是可能是最大值情况这个很直观
• 如果说根与左树差一而右树不差一，那么右树给的递增/递减结果是0，当前节点从中得到的递增/递减结果是1。（递增 + 递减 - 1）的（-1）将这个情况给减去了，剩下的就是根与左树的递增/递减值
• 如果说根与右树差一而左树不差一，同理
• 如果说根与左右树都不差一，那么当前节点的递增/递减节点都分别是1，那么（递增 + 递减 - 1）= （1 + 1 - 1） = 1，说明当前节点的最大连续递增/递减节点是1，这也符合情况

我觉得三种情况是比较好分析出来的，但是第三种情况其实可以用（递增+递减-1）这一句话来表达，是比较隐含的insight。

class Solution {
private:
    int gl_max = 0;
    struct Result
    {
        int val;
        int inc;
        int dec;
        
        Result(int v, int i, int d) : val(v), inc(i), dec(d) {}
    };
    
    Result* helper(TreeNode* root)
    {
        if (!root) return nullptr;
        Result* left = helper(root->left);
        Result* right = helper(root->right);
        int inc = 1, dec = 1;
        if (left && root->val - left->val == 1) inc = left->inc + 1;
        else if (left && left->val - root->val == 1) dec = left->dec + 1;
        if (right && root->val - right->val == 1) inc = max(inc, right->inc + 1);
        else if (right && right->val - root->val == 1) dec = max(dec, right->dec + 1);
        gl_max = max(gl_max, inc + dec - 1);
        return new Result(root->val, inc, dec);
    }
    
    
public:
    int longestConsecutive(TreeNode* root) 
    {
        helper(root);
        return gl_max;
    }
};

272. Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

这道题，我是这么想。recursion中，将比target更小的数放在stack里，一旦找到比target更大的数了，就将之和之后遍历的数与stack中比较，取离target更近的那个数放进result vector。挺直观的，写的时候注意终止条件：

• 我们放到k==res.size()为止
  • 如果比target小的数先都放进res了（甚至没有比target小的数），但是还没终止的话，要注意之后的遍历每一个数都要放进res
  • 如果比target大的数先都放进res了（甚至没有比target大的数），但是还没终止的话，要把stack里的数推到res里

class Solution {
private:
    void inorder_add_k(TreeNode* root, double target, stack<int> &inorder, bool &end, vector<int> &res, int k)
    {
        if (!root) return;
        inorder_add_k(root->left, target, inorder, end, res, k);
        if (target <= root->val) end = true;
        if (!end) inorder.push(root->val);
        else
        {
            while (inorder.size() && res.size() < k)
            {
                int last = inorder.top();
                if (target - last <= root->val - target) 
                { res.push_back(last); inorder.pop();} 
                else 
                { res.push_back(root->val); break; }
            }
            if (res.size() == k) return;
            else if (inorder.empty()) res.push_back(root->val);
        }
        inorder_add_k(root->right, target, inorder, end, res, k);
    }
    
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) 
    {
        stack<int> inorder;
        bool end = false;
        vector<int> res;
        inorder_add_k(root, target, inorder, end, res, k);
        // if we've exhausting elements > target
        while (res.size() != k)
        {
            res.push_back(inorder.top());
            inorder.pop();
        }
        return res;
    }
};

这样的解法最坏情况也是O（n+k）的。另外参考评论区，还有一种解法，可以先找到离target最近的那个值，需要O（h）。然后用两个pointer，一个往小了去，一个往大了去，每次pointer的遍历时间也是O（h）。这样就一共是O（kh）时间。这样的想法的本质其实就是在一个sorted array找到k nearest elements，不过由于这是树，这种iterator的操作比较少见，因为不是O（1）的。让我来写写看：