二叉树的DFS：
⭕️LC144 Binary Tree Preorder Traversal
⭕️LC94 Binary Tree Inorder Traversal
⭕️LC145 Binary Tree Postorder Traversal

二叉树的BFS:
⭕️LC102 Binary Tree Level Order Traversal
⭕️LC107 Binary Tree Level Order Traversal II
⭕️103. Binary Tree Zigzag Level Order Traversal
⭕️LC662 二叉树的最大宽度
⭕️LC199 二叉树的右视图
 LC513 找树左下角的值
 LC116 填充每个节点的下一个右侧节点指针
 LC117 填充每个节点的下一个右侧节点指针II
LC919 完全二叉树插入器
 LC1302 层数最深叶子节点的和

序列化与反序列化二叉树：
⚠️LC655 输出二叉树
⭕️LC297 Serialize and Deserialize Binary Tree[前序遍历，nullptr要有占位符]

二叉树的坐标化：
LC665 输出二叉树
 LC987 二叉树的垂序遍历

根据遍历序列重建二叉树：
⭕️LC106 Construct Binary Tree from Inorder and Postorder Traversal
⭕️LC105 Construct Binary Tree from Preorder and Inorder Traversal

向下路径与叶子路径：
LC129 Sum Root to Leaf Numbers
⭕️LC104 Maximum Depth of Binary Tree
⚠️LC111 Minimum Depth of Binary Tree
LC257 二叉树的所有路径
 LC112 Path Sum
LC113 Path Sum II
LC437 Path Sum III

折返路径：
LC543 二叉树的直径
 LC687 最长同值路径
 LC124 折返路径和
 LC110 平衡二叉树

两个二叉树的关系：
⭕️LC100 相同的树
⭕️LC面试题26. 树的子结构
 LC572 Subtree of Another Tree
LC面试题04.10 检查子树
 LC617 合并二叉树

对称的二叉树：
❌LC226 求二叉树的镜像
❌LC101 Symmertic Tree

最低公共祖先：
LC235 Lowest Common Ancestor of a Binary Search Tree
LC236 Lowest Common Ancestor of a Binary Tree
LC742 二叉树最近的叶节点

其他：
⚠️LC222 完全二叉树的节点个数
 LC545 二叉树的边界
 LC114 二叉树展开为链表

子树类问题：
LC250 统计同值子树
 LC1120 子树的最大平均值

二叉树的DFS

LC144 Binary Tree Preorder Traversal
LC94 Binary Tree Inorder Traversal
LC145 Binary Tree Postorder Traversal

递归方法

略。

栈

栈的最大长度是此二叉树的深度。对于比较平衡的二叉树来说，用栈来模拟递归是很实用的方法。但当二叉树平衡性很差，甚至退化成链表的时候，就要考虑不使用栈的Morris遍历了。

前序遍历

access
preorderTraversal(root->left)
preorderTraversal(root->right)

思考使用递归实现前序遍历的时候，函数调用栈的样子。前序遍历的过程中遇到节点就会访问，并且一路向左。因此函数调用栈里保存的信息应该是每一处的右节点。我们每次一直向左走到头的时候，就要去访问其父亲节点的右节点了。思路：

- 遇到节点就访问，并将右节点压入栈中，之后向左走，直到走到头。
- 如果走到头就从栈里取出一个节点，重复上面一步。
- 如果栈空了，那么遍历结束了。

可能的优化：

- 将右节点压入栈前，检查右节点是否为空。感觉没有必要。因为增加了一个流程控制语句。不如让`while`循环直接判断。
- 将栈是否为空的判断语句放在外层`while`循环处。并将第一个节点推入栈中。就像调用递归的preorderTraversal一样，需要先把root传入。

前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res{};
        vector<TreeNode*> stack{};
        while(true)
        {
            while(root)
            {
                if(root->right)
                    stack.push_back(root->right);
                // visit
                res.push_back(root->val);
                root = root->left;
            }

            if(stack.empty())
            {
                break;
            }
            root = stack.back();
            stack.pop_back();
        }
        return res;
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res{};
        vector<TreeNode*> stack{};
        stack.push_back(root);
        while(!stack.empty())
        {
            auto rt = stack.back();
            stack.pop_back();
            while(rt)
            {
                res.push_back(rt->val);
                stack.push_back(rt->right);
                rt = rt->left;
            }
        }
        return res;
    }
};

中序遍历

preorderTraversal(root->left)
access
preorderTraversal(root->right)

中序遍历时，遇到节点不会直接访问，而是先深入到左侧节点。直到左侧节点为空，才会访问该节点。之后访问父节点，最后是右子树。因此函数调用栈里保存应该是父节点的信息。

- 每次遇到节点直接压入栈中即可。
- 不断向左移动，直到该节点为空（注意此时这个空节点的父亲节点已经被压入栈中）。这和递归调用的函数调用栈是一致的，我们会持续调用`preorderTraversal(root->left)`，直到`root->left == nullptr`时，这个函数会直接返回。返回后就马上开始访问，然后再用右子树重复之前的过程。
- 如果栈空了，遍历结束。
- 如果栈非空，从栈中取出一个节点，访问，移动到他的右节点，重复上述过程。

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res{};
        vector<TreeNode*> stack{};
        
        while(true)
        {
            while(root)
            {
                // move to its left subtree and push its parent node into stack
                stack.push_back(root);
                root = root->left;
            }
            // if the stack is empty, traversal ends
            if(stack.empty()) break;
            // get a node from the stack and visit.
            root = stack.back();
            stack.pop_back();
            res.push_back(root->val);
            // move to its right subtree, do this again
            root = root->right;
        }

        return res;
    }
};

后续遍历

如果一个节点是右孩子，或没有兄弟节点的左孩子，访问该节点后会立刻访问该节点的父节点。直接中栈来实现后续遍历非常麻烦。我们可以采用一些小手段。仔细观察后续遍历的序列，可以发现其遍历序列的逆序非常类似一个先右子树，后左子树的的前序遍历。因此我们可以用栈来实现一个先右后左的前序遍历，然后将结果逆序即可。采用两个栈来实现是没有必要的，reverse算法要比从栈里逆序效率要高。

先左后右的前序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res{};
        vector<TreeNode*> stack{};
        stack.push_back(root);
        while(!stack.empty())
        {
            root = stack.back();
            stack.pop_back();
            while(root)
            {
                // visit the node
                res.push_back(root->val);
                // push its LEFT subtree into the stack
                stack.push_back(root->left);
                // move to its RIGHT subtree
                root = root->right;
            }
        }
        // reverse the result
        reverse(res.begin(), res.end());
        return res;
    }
};

Morris遍历

Morris遍历是一个不断地给节点找后继节点的过程。

中序遍历

空间复杂度为$O(1)$的遍历方法。代价是在遍历过程中会修改树，因此不能中途退出，否则树的结构会被破坏。

前序遍历回顾：

访问当前节点
尝试进入当前节点左子树
- 如果当前节点存在左子树，进入其左子树，回到开头
- 如果当前节点不存在左子树，尝试进入其右子树
  - 如果当前节点存在右子树，进入其右子树，回到开头。
  - 如果当前节点不存在右子树，进入其第一个存在右子树的祖先节点的右子树。（这就是为什么我们要沿着左子树往下走，并把沿途的右子树都压入栈中的原因）
    - 如果不存在有右子树的祖先节点祖先节点（即栈空了），结束。

中序遍历回顾：

尝试进入当前节点左子树
- 如果当前节点存在左子树，进入其左子树，回到开头。
- 如果当前节点不存在左子树，访问当前节点，并尝试进入当前节点右子树
  - 如果当前节点存在右节点，进入右节点，回到开头。
  - 如果当前节点不存在右子树，访问第一个将其作为左子树的祖先节点(即后继节点。对于存在右子树的节点，其后继节点为其右子树中最左节点。对于不存在右子的节点，其后继为第一个将其作为左子树的祖先节点。由于一般的二叉树节点设计中，都不提供进入父节点的指针。因此，我们在使用辅助栈的中序遍历的程序中，要一直沿着左子树走，并把经历的节点压入栈中。这些节点都是以后的【第一个将其作为左子树的祖先节点】)
    - 如果不存在将其作为左子树的祖先节点(即栈空了)，结束。

一个节点的【后继节点】是：

如果这个节点的右子树非空，【后继节点】是右子树中的最小节点（右子树中一直沿着左走到头）
如果这个节点的右子树是空的，【后继节点】就是第一个把该节点当作左孩子的祖先节点（有可能不存在）。

一个节点的【前序节点】是：

如果这个节点的左子树非空，【前序节点】就是左子树中的最大节点（左子树中一直沿着右走到头）
如果这个节点的左子树是空的,【前序节点】就是第一个把该节点当作右孩子的祖先节点（有可能不存在）。

前序与后继关系的相互性：一个节点n如果是另一个节点m的前序节点，那么节点m一定是n的后继节点。

二叉搜索树的中序遍历可以排序输出树中所有元素。所以中序遍历的过程，就是一个不断寻找当前节点的后继节点的过程。

当我们从根节点一路向左，沿路设置所有节点的前序节点的右孩子指针为该节点（等同于每个节点的后继节点设置为其右孩子，但是我们在当前节点处不能这么，因为会失去其右指针）。寻找每个节点的前驱节点时，当且仅当我们遇到树的最左边节点时，才会有左子树是空的的情况。并且该该节点不存在【前驱节点】（因为我们一路往左下来的）。之后打印该节点并进入该节点的右子树重复上面的过程。同时，在进入右子树时，所有比右子树里小的（右子树的所有前置节点）都被访问过了，这个时候如果再遇到左子树是空的的情况，我们也可以认为不存在【前驱节点】了，直接访问即可。然后再进入右子树的过程中，就可能发生顺着之前被设置的右孩子指针进入【后继节点】的情况，这个时候要重新检查该【后继节点】的前驱节点是不是自己，是自己就恢复原状，否则死循环。

思路（从根节点开始）

如果该节点没有左孩子，访问该节点，进入该节点的右孩子
如果该节点有左孩子，寻找该节点的【前序节点】
- 如果该节点的【前序节点】的右孩子是该节点本身
  - 访问该节点。
  - 设置该节点的【前序节点】的右孩子为空。
  - 进入该节点的右孩子。
- 如果该节点的【前序节点】的右孩子为空
  - 设置该节点的【前序节点】的右孩子为该节点。
  - 进入该节点的左孩子。

code

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        auto res = vector<int>{};
        while(root)
        {
            // no left child, we cannot find its predecessor
            // just visit it
            if(!root->left)
            {
                res.push_back(root->val);
                root = root->right;
                continue;
            }

            // root has a left child, we have to find its
            // predecessor and link them together
            auto pre = root->left;
            while(pre->right && pre->right != root)
            {
                pre = pre->right;
            }
            // situation1. we have never link root's 
            // predecessor with it
            if(pre->right == nullptr)
            {
                pre->right = root;
                root = root->left;
            }
            // situation2. we have already linked, time to visit.
            else
            {
                pre->right = nullptr;
                res.push_back(root->val);
                // there is no need to move left anymore
                // we have just came back from its left
                root = root->right;
            }
            
        }

        return res;
    }
};

Morris前序遍历

调整访问节点的位置，从【该前驱节点已经被访问过】移动到【该前去节点还未被访问过】，即是前序遍历。
思路（从根节点开始）

如果该节点没有左孩子，访问该节点，进入该节点的右孩子

如果该节点有左孩子，寻找该节点的【前序节点】

如果该节点的【前序节点】的右孩子是该节点本身
- 设置该节点的【前序节点】的右孩子为空。
- 进入该节点的右孩子。

如果该节点的【前序节点】的右孩子为空

访问该节点。
设置该节点的【前序节点】的右孩子为该节点。

进入该节点的左孩子。

code

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        auto result = vector<int>{};
        while(root != nullptr){
            if(root->left == nullptr){
                result.push_back(root->val);
                root = root->right;
            }else{
                auto pre = root->left;
                while(pre->right != nullptr && pre->right != root) pre = pre->right;
                if(pre->right == nullptr){
                    result.push_back(root->val);
                    pre->right = root;
                    root = root->left;
                }else{
                    pre->right = nullptr;
                    root = root->right;
                }
            }
        }
        return result;
    }
};

Morris后序遍历

Morris后序遍历需要设置一个哨兵节点，使这个哨兵节点的左孩子为树的根节点，右孩子为空。
思路（从哨兵节点开始）

如果该节点没有左孩子，访问该节点，进入该节点的右孩子
如果该节点有左孩子，寻找该节点的【前序节点】
- 如果该节点的【前序节点】的右孩子是该节点本身
  - 逆序访问该节点的左孩子到该节点的【前序节点】
  - 设置该节点的【前序节点】的右孩子为空。
  - 进入该节点的右孩子。
- 如果该节点的【前序节点】的右孩子为空
  - 设置该节点的【前序节点】的右孩子为该节点。
  - 进入该节点的左孩子。

code

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        auto result = vector<int>{};
        auto sentinel = new TreeNode(INT_MAX);
        sentinel->left = root;
        root = sentinel;
        while(root){
            if(!root->left){
                root = root->right;
            }else{
                auto pre = root->left;
                while(pre->right && pre->right != root) pre = pre->right;
                if(pre->right == nullptr){
                    pre->right = root;
                    root = root->left;
                }else{
                    //visit start
                    auto s = stack<int>{};
                    auto pre2 = root->left;
                    while(pre2 != root){
                        s.push(pre2->val);
                        pre2 = pre2->right;
                    }
                    while(!s.empty()){
                        result.push_back(s.top());
                        s.pop();
                    }
                    //visit end
                    pre->right = nullptr;
                    root = root->right;
                }
            }
        }
        return result;
    }
};

参考：

面试算法：二叉树的Morris遍历算法 - 望月从良 - 简书
 经典算法小评(2)——Morris树遍历算法 - 风之筝 - GitHub Pages 有图解！
Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）- AnnieKim - 博客园 有图解！

二叉树的BFS

层序遍历经常犯的错误：for循环不要写成i < queue.size()，这样就失去记录level_size的意义了。

剑指Offer 32
LC102 Binary Tree Level Order Traversal
LC107 Binary Tree Level Order Traversal II

类似BFS，我们维护一个队列，每次从队列里取出一个节点，然后再将该节点的左右孩子（如果有）再push进队列里即可。

LC102和LC107都要求将结果分层放入vector中，因此我们需要统计下一层有几个节点和这层还剩下多少节点。

因为层序遍历保证不遍历完当前层不会去遍历下一层：

每次往队列里推入节点时，都是下一层的节点，这时我们就增加下一层节点计数器。
当前层节点计数器不等于0。每次我们从队列中取出节点时，都是当前层的节点，减少当前层节点计数器。
当前层节点计数器为0。将下一层节点计数器的值赋给当前层节点计数器，下一层计数器清零，继续循环。
实现细节注意：
换层时别忘了下层计数器清零。
换层时还要检查一下下一层计数器是否为0，如果为0，就不需要换层了。这里如果忘了检查的话，会多给结果在最后构造一个空数组。

更清晰的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // if the tree is empty, return empty.
        if(!root) return {};
        queue<TreeNode*> queue{};
        vector<vector<int>> res{{}};
        // push the root into the queue
        queue.push(root);
        // the nodes left in current level
        size_t cur_nums = 1;
        // the nodes in next level
        size_t next_nums = 0;

        while(!queue.empty())
        {
            root = queue.front();
            queue.pop();
            // decrease the nodes in current level
            --cur_nums;
            // push the node val into res
            res.back().push_back(root->val);
            // push the left and right children into the queue
            if(root->left)
            {
                queue.push(root->left);
                ++next_nums;
            }
            if(root->right)
            {
                queue.push(root->right);
                ++next_nums;
            }
            // check if cur level is empty 
            // check if next level is not empty
            if(cur_nums == 0 && next_nums != 0)
            {
                // change cur_nums into next_nums
                cur_nums = next_nums;
                // next_nums reset
                next_nums = 0;
                // create new "level" in the res vector
                res.emplace_back();
            }
        }

        return res;
    }
};

2019年8月的代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        auto q = queue<TreeNode* >{};
        auto v = vector<vector<int> >{{}};
        size_t nodes_in_next_level = 0;
        size_t nodes_left_in_this_level = 1;
        q.push(root);
        while(!q.empty()){
            auto cur = q.front();
            //visit cur
            if(nodes_left_in_this_level > 0){
                v.back().push_back(cur->val);
                --nodes_left_in_this_level;//更新这层剩下的节点数
            }
            else//nodes_left_in_this_level == 0，换到下一层
            {
                nodes_left_in_this_level = nodes_in_next_level - 1;
                nodes_in_next_level = 0;
                v.push_back({cur->val});
            }
            //visit end
            if(cur->left){
                q.push(cur->left);
                ++nodes_in_next_level;//统计下一层有几个节点
            }
            if(cur->right){
                q.push(cur->right);
                ++nodes_in_next_level;//统计下一层有几个节点
            }
            q.pop();
        }
        return v;
    }
};

二叉树的最大宽度

LC662 二叉树的最大宽度

层序遍历二叉树。层序遍历时，每次遍历完一层，队列的长度就正好是下一层的节点树。在队列中不但记录节点，也记录下来节点的编号。类似二叉堆那样，一个节点编号为idx，他的左孩子编号是2 * idx，右孩子编号是2 * idx + 1。记录下每一层的第一个节点和最后一个节点的编号。他们的差就是这一层的宽度。

注意：这个题有一个全是左子树的测试用例，会导致编号溢出。所以我们每次都把编号”归一化”一下，让下一层的所有idx都统一减去一个值，就可以抑制序号的增长速度，也不会影响距离的计算。

2020/8/21更新：LeetCode新加入了undefined behaviour santinizer，使得上面的方法也无法通过全是左子树的测试用例的测试用例。我们需要将和id相关的变量改为uint64_t才行。

注意：每一层的first_idx和last_idx被初始化为0。当这一层只有一个节点时，下面的形式会导致last_idx仍未0，使last_idx - first_idx计算溢出。

if(i == 0)
{
first_idx = idx;
}
else if(i == level_size - 1)
{
last_idx = idx;
}

应该改为

if(i == 0)
{
first_idx = idx;
}
if(i == level_size - 1)
{
last_idx = idx;
}

即i == 0和i == level_size - 1并不是互斥的。当只有一个节点时，0 == level_size - 1。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
      auto q = queue<pair<TreeNode*, uint64_t>>{};
      q.emplace(root, uint64_t{0});
      uint64_t ans = 0;

      while(!q.empty())
      {
        auto level_size = q.size();
        uint64_t first_idx, last_idx = 0;
        for(auto i = size_t{}; i < level_size; ++i)
        {
          auto [node, idx] = q.front();
          q.pop();

          if(i == 0)
          {
            first_idx = idx;
          }
          
          if(i == level_size - 1)
          {
            last_idx = idx;
          }

          if(node->left)
          {
            q.emplace(node->left, idx * 2 + 1);
          }
          if(node->right)
          {
            q.emplace(node->right, idx * 2 + 2);
          }
        }

        ans = max(ans, last_idx - first_idx + 1);
      }

      return ans;
    }
};

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        queue<pair<TreeNode*, int>> queue{};
        queue.push({root, 1});
        int width = 0;
        while(!queue.empty())
        {
            // after processing a whole level
            // the num of nodes in next level is the size of queue
            int first_idx = 0;
            int last_idx = 0;
            auto level_size = queue.size();
            for(size_t i = 0; i < level_size; ++i)
            {
                // get a node from the queue
                auto [node, idx] = queue.front();
                
                queue.pop();
                // save the idx of first and last node
                if(i == 0) first_idx = idx;
                if(i == level_size - 1) last_idx = idx;

                // push its children into the queue
                if(node->left)
                {
                    queue.push({node->left, 
                    2 * idx - first_idx + 1});
                }
                if(node->right)
                {
                    queue.push({node->right, 
                    2 * idx + 1 - first_idx + 1});
                }
            }
            // the whole level is processed, compute the width
            width = max((last_idx - first_idx + 1), width);
        }

        return width;
    }
};

二叉树的右视图

LC199 二叉树的右视图
层次遍历，每次都把每一层最后一个节点的值放进结果容器中即可。

code

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        // we a level order traversal
        vector<int> res{};
        queue<TreeNode*> queue{};
        queue.push(root);
        while(!queue.empty())
        {
            // at the beginning of each iteration, queue size
            // is the number of nodes in this level
            auto level_size = queue.size();
            // pop the queue, push their children back
            for(int i = 0; i < level_size ; ++i)
            {
                root = queue.front();
                queue.pop();
                if(root->left)
                {
                    queue.push(root->left);
                }
                if(root->right)
                {
                    queue.push(root->right);
                }
            }
            // root is now the last element in this level
            // , which is visible in the right sideview
            res.push_back(root->val);
        }
        return res;
    }
};

二叉树左下角的值

LC513 找树左下角的值
层次遍历，储存每层第一个节点即可。

code

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> queue{};
        queue.push(root);
        TreeNode* bottomLeftNode = nullptr;
        while(!queue.empty())
        {
            auto level_size = queue.size();
            for(size_t i = 0; i < level_size; ++i)
            {
                root = queue.front();
                queue.pop();

                if(root->left) queue.push(root->left);
                if(root->right) queue.push(root->right);
                // save the first node in each level
                if(i == 0)
                {
                    bottomLeftNode = root;
                }
            }
        }

        return bottomLeftNode->val;
    }
};

Zigzag遍历

剑指Offer 32
103. Binary Tree Zigzag Level Order Traversal

思路：

利用栈的FIFO特点来实现每一层的逆序
用一个栈来存储当前层的节点，另一个栈存储下一层的节点。如果当前层的栈空了，交换两个栈。
不能只用一个栈，因为那样会使得下一层的节点先于这一层的节点被访问。
先把根节点入栈当前层
奇数层先入栈右孩子，偶数层先入栈左孩子

code

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return {};
        auto curStack = new stack<TreeNode* >{};
        auto nextStack = new stack<TreeNode* >{};
        auto result = vector<vector<int> >{{}};
        auto odd_even_flag = true;
        
        size_t nodes_in_next_level = 0;
        size_t nodes_left_in_this_level = 1;
        
        curStack->push(root);
        
        while(!curStack->empty()){
            auto cur = curStack->top();
            //visit cur
            if(nodes_left_in_this_level > 0){
                result.back().push_back(cur->val);
                --nodes_left_in_this_level;
            }else{
                nodes_left_in_this_level = nodes_in_next_level - 1;
                nodes_in_next_level = 0;
                result.push_back({cur->val});
            }
            //end visit
            if(odd_even_flag){
                if(cur->left){
                    nextStack->push(cur->left);
                    ++nodes_in_next_level;
                }
                if(cur->right){
                    nextStack->push(cur->right);
                    ++nodes_in_next_level;
                }  
            }else{
                if(cur->right){
                    nextStack->push(cur->right);
                    ++nodes_in_next_level;
                }                
                if(cur->left){
                    nextStack->push(cur->left);
                    ++nodes_in_next_level;
                }                
            }           
            curStack->pop();
            if(curStack->empty()) {
                swap(curStack, nextStack);
                odd_even_flag = !odd_even_flag;
            }
        }
        delete curStack;
        delete nextStack;
        return result;
    }
};

层序下一节点

LC116 填充每个节点的下一个右侧节点指针

思路一：
层序遍历。用queue.size()和for循环来定位每一层的开始和结束。记录前一个节点的指针，不断将前一个节点的指针设置为当前节点。但是这样做不满足题目空间复杂度为$O(1)$的要求。

层序遍历经常犯的错误：for循环不要写成i < queue.size()，这样就失去记录level_size的意义了。

code

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;

        queue<Node*> queue{};
        queue.push(root);

        while(!queue.empty())
        {
            auto level_size = queue.size();
            Node* preNode = nullptr;
            for(size_t i = 0; i < level_size; ++i)
            {
                auto cur = queue.front();
                queue.pop();
                if(cur->left) queue.push(cur->left);
                if(cur->right) queue.push(cur->right);
                
                if(preNode) preNode->next = cur;
                preNode = cur;
                
            }
            cout<<endl;
        }

        return root;

    }
};

思路二：
利用完美二叉树的性质：
一个节点的左孩子的next必然是其右节点。一个节点的右孩子的next是该节点next的左孩子。从根节点开始，不断设置下一层的next指针。再移动到下一层的最左侧，因为此时这一层的next指针已经在上层被设置好，所以可以用这层的next设置下一层的next。循环直到最后一层即可。空间复杂度为$O(1)$满足题目要求。

code

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return nullptr;

        auto rt = root;
        while(root->left)
        {
            auto first = root;
            while(root->next)
            {
                root->left->next = root->right;
                root->right->next = root->next->left;
                root = root->next;
            }
            root->left->next = root->right;
            root = first->left;
        }
        return rt;
    }
};

LC117 填充每个节点的下一个右侧节点指针II

同上题，取消了完美二叉树的假设。

一个节点的左孩子的next：

如果有右孩子，则是右孩子
如果没有右孩子，则是该节点的右侧(next, next的next, …)的一个有孩子节点的第一个孩子。

一个节点的右孩子的next：

该节点的右侧(next, next的next, …)的一个有孩子节点的第一个孩子。

下一层的第一个节点是：

如果这一层的第一个节点有左孩子，是其左孩子
否则，如果这一层的第一个节点有右孩子，是其右孩子
否则，是该节点的右侧(next, next的next, …)的一个有孩子节点的第一个孩子。

code

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        
        auto rt = root;
        while(root)
        {
            auto first = root;

            while(root)
            {
                if(root->left && root->right)
                {
                    root->left->next = root->right;
                    root->right->next = child_next(root);
                    
                }
                else if(root->left)
                {
                    root->left->next = child_next(root);
                }
                else if(root->right)
                {
                    root->right->next = child_next(root);
                }
                // else !root->left && !root->right do nothing
                root = root->next;
            }
            if(first->left)
            {
                root = first->left;
                continue;
            }

            if(first->right)
            {
                root = first->right;
                continue;
            }
            
            root = child_next(first);
        }
        return rt;
    }

    static Node* child_next(Node* root)
    {
        if(!root) return nullptr;
        if(!root->next) return nullptr;
        root = root->next;
        while(root)
        {
            if(root->left) return root->left;
            if(root->right) return root->right;
            root = root->next;
        }
        return nullptr;
    }
};

完全二叉树插入器

LC919 完全二叉树插入器

维护一个队列。该队列类似层序遍历二叉树时的队列。
队列前端的节点一定是当前树中左右孩子还未被填满的最左侧节点。
每次向树中插入新节点时：
- 检查队列首节点是否有左孩子，如果没有就将新节点插入到左孩子的位置，并把新节点放入队列
- 如果有左孩子，且该节点还在队列中，则该节点必然没有右孩子，将新节点放在队列该节点的右孩子处。把新节点放入队列。将该节点从队列中删掉。
从最初给定的树构建队列时：
- 从左到右层序遍历给定的树
- 如果左孩子或右孩子有一个缺失，就把该节点放入队列
既然叫插入器，那么由调用该插入器的一方保证管理资源。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class CBTInserter {
public:
    CBTInserter(TreeNode* root) 
    :m_root{root}
    ,m_parent{}
    {
        build_queue(root);
    }

    void build_queue(TreeNode* root)
    {
        auto bfs_queue = queue<TreeNode*>{};
        bfs_queue.push(root);
        while(!bfs_queue.empty())
        {
            auto node = bfs_queue.front();
            bfs_queue.pop();
            if(!(node->left && node->right))
            {
                m_parent.push(node);
            }

            if(node->left)
            {
                bfs_queue.push(node->left);
            }

            if(node->right)
            {
                bfs_queue.push(node->right);
            }
        }
    }
    
    int insert(int v) {
        auto parent = m_parent.front();
        if(!parent->left)
        {
            parent->left = new TreeNode{v};
            m_parent.push(parent->left);
        }
        else if(!parent->right)
        {
            parent->right = new TreeNode{v};
            m_parent.push(parent->right);
            m_parent.pop();
        }

        return parent->val;

    }
    
    TreeNode* get_root() const {
        return m_root;
    }

private:
    TreeNode* m_root;
    queue<TreeNode*> m_parent;
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(v);
 * TreeNode* param_2 = obj->get_root();
 */

层数最深叶子节点的和

LC1302 层数最深叶子节点的和

层序遍历，记录每一层的和即可。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        if(!root)
        {
            return 0;
        }

        auto bfs_queue = queue<TreeNode*>{};
        bfs_queue.push(root);
        auto level_size = size_t{1};
        auto sum = 0;
        while(!bfs_queue.empty())
        {
            auto cur_level_size = size_t{};
            sum = 0;
            for(auto i = size_t{}; i < level_size; ++i)
            {
                auto node = bfs_queue.front();
                bfs_queue.pop();

                sum += node->val;

                if(node->left)
                {
                    bfs_queue.push(node->left);
                    ++cur_level_size;
                }

                if(node->right)
                {
                    bfs_queue.push(node->right);
                    ++cur_level_size;
                }
            }

            level_size = cur_level_size;
        }

        return sum;
    }
};

二叉树的坐标化

利用一个有序数对$(x,y)$来确定二叉树中的每一个节点：

根节点的坐标为$(0,0)$
一个节点的坐标为$(x,y)$，则其左孩子为$(x + 1, 2y)$，右孩子为$(x + 1, 2y + 1)$
一个非根节点的坐标为$(x,y)$，则其父节点的坐标为$(x - 1, \lfloor{\frac{y}{2}}\rfloor)$

LC742 二叉树最近的叶节点也可以通过坐标化来求距离。但其测试用例中有层数过多的二叉树，导致坐标溢出。

overflow code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class tree_index
{
public:
    struct index
    {
        size_t x;
        size_t y;

        index left_child() const noexcept
        {
            return {x + 1, y * 2};
        }

        index right_child() const noexcept
        {
            return {x + 1, y * 2 + 1};
        }

        index parent() const noexcept
        {
            if(x == 0)
            {
                return *this;
            }

            return {x - 1, y / 2};
        }

        vector<index> down_path() const noexcept
        {
            if(x == 0)
            {
                return {*this};
            }

            auto path = vector<index>(x + 1);
            auto idx = *this;
            for(auto i = path.rbegin(); i != path.rend(); ++i)
            {
                *i = idx;
                idx = idx.parent();
            }

            return path;
        }

        static size_t distance(const index& lhs, const index& rhs) noexcept
        {
            auto lpath = lhs.down_path();
            auto rpath = rhs.down_path();

            // get the iterators for lowest common ancestor
            auto [llca, rlca] = mismatch(lpath.begin(), lpath.end(), rpath.begin(), rpath.end(),
            [](const auto& l, const auto& r)
            {
                return l.x == r.x && l.y == r.y;
            });

            return (lpath.end() - llca) + (rpath.end() - rlca);
        }
    };

    explicit tree_index(TreeNode* root, int target) noexcept
    :m_target_val{target}
    {
        if(!root)
        {
            return;
        }

        m_indices[root] = index{0, 0};
        tree_index_impl(root);
    }

    int closest_leaf()
    {
        auto dist = UINT32_MAX;
        auto res = 0;
        for(auto leaf : m_leaf_nodes)
        {
            // cout<<"form: "<<leaf->val<<" "<<m_indices[leaf].x<<","<<m_indices[leaf].y<<" to "
            // <<m_indices[m_target].x<<","<<m_indices[m_target].y<<"\n";
            auto d = index::distance(m_indices[leaf], m_indices[m_target]);

            if(dist > d)
            {
                dist = d;
                res = leaf->val;
            }
        }

        return res;
    }

private:

    void tree_index_impl(TreeNode* root) noexcept
    {
        if(root->val == m_target_val)
        {
            m_target = root;
        }

        if(!root->left && !root->right)
        {
            m_leaf_nodes.insert(root);
        }
        
        if(root->left)
        {
            m_indices[root->left] = m_indices[root].left_child();
            tree_index_impl(root->left);
        }

        if(root->right)
        {
            m_indices[root->right] = m_indices[root].right_child();
            tree_index_impl(root->right);
        }
    }

    unordered_map<TreeNode*, index> m_indices = {};
    unordered_set<TreeNode*> m_leaf_nodes = {};
    int       m_target_val = 0;
    TreeNode* m_target = {};
};
class Solution {
public:
    int findClosestLeaf(TreeNode* root, int k) {
        auto tidx = tree_index{root, k};
        return tidx.closest_leaf();
    }

    
};

LC987 二叉树的垂序遍历

按要求将二叉树所有节点坐标化后排序。再将排序好的数组按X坐标分割即可。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
private:
    struct point
    {
        int x;
        int y;
        int val;

        friend bool operator<(const point& lhs, const point& rhs)
        {
            return lhs.x != rhs.x ? 
                   lhs.x <  rhs.x :
                   lhs.y != rhs.y ?
                   lhs.y >  rhs.y :
                   lhs.val < rhs.val;
        }
    };

    vector<point> m_points;
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root)
        {
            return {};
        }

        m_points.push_back(point{0, 0, root->val});
        build_map(root, m_points.back());

        sort(m_points.begin(), m_points.end());
        auto res = vector<vector<int>>{};

        for(auto it = m_points.begin(); it != m_points.end(); )
        {
            auto last = it;
            while(last != m_points.end() && last->x == it->x)
            {
                ++last;
            }

            res.emplace_back(last - it);
            transform(it, last, res.back().begin(), [](const auto& pt)
            {
                return pt.val;
            });

            it = last;
        }

        return res;
    }

    void build_map(TreeNode* root, point pt)
    {
        if(root->left)
        {
            m_points.push_back(point{pt.x - 1, pt.y - 1, root->left->val});
            build_map(root->left, m_points.back());
        }

        if(root->right)
        {
            m_points.push_back(point{pt.x + 1, pt.y - 1, root->right->val});
            build_map(root->right, m_points.back());
        }
    }
};

输出二叉树

LC655 输出二叉树

先观察给的例子，我们可以发现：

输出的数组行数为二叉树的最大深度depth，列数为二叉树的width = 2 ^ depth - 1。
先构造这么大的一个数组，并给他填充好空字符串""
根节点必然位于第0层的中央，也就是其坐标为[0][width / 2];
再观察从第1层开始，每个节点和其父节点的间隔为diff = 2 ^ (depth - cur_level - 1)。
因此我们如果有了父节点的坐标，就可以直接推出其左右孩子的坐标。
那么我们就在这个树上做一个层序遍历就可以了。层序遍历用的队列储存pair<TreeNode*, int>，其中的int为这个node在这一行的坐标。
每次从队伍中取出节点，就根据他的坐标给他放入矩阵相应位置。然后再检查他的左右孩子，如果有的话，再根据他自己的坐标算出孩子的坐标。

code

class Solution {
public:
    vector<vector<string>> printTree(TreeNode* root) {
        // we first find the depth of the given tree
        auto depth = depthTree(root);
        // width = 2 ^ depth - 1
        auto width = 2;
        for(auto i = 1; i < depth; ++i)
        {
            width *= 2;
        }
        --width;

        // we create a matrix that is just the size of 
        // the result and fill it in properly
        auto res = 
        vector<vector<string>>(depth, vector<string>(width, ""));

        // we start to do level order traversal on the tree
        queue<pair<TreeNode*, int>> queue;
        // the pos for root should resides at the middle of the 
        // first row, which is width / 2
        queue.push({root, width / 2});
        // the distance between a node and its parent
        // could be computed by the following formula
        // diff = 2 ^ (depth - cur_level - 1)
        // we could initilize the level1 distance and
        // then divide it by 2 at the end of every level
        int diff = (width + 1) / 4;
        int cur_level = 0;
        while(!queue.empty())
        {
            int cur_level_size = queue.size();
            for(int i = 0; i < cur_level_size; ++i)
            {
                // take a node from the queue
                auto [node, idx] = queue.front();
                queue.pop();

                // put the node into its right pos
                res[cur_level][idx] = to_string(node->val);

                if(node->left)
                {
                    queue.push({node->left, idx - diff});
                }

                if(node->right)
                {
                    queue.push({node->right, idx + diff});
                }
            }
            diff = diff / 2;
            ++cur_level;
        }
        return res;
    }

    int depthTree(TreeNode* root)
    {
        if(!root) return 0;
        return max(depthTree(root->left), 
                   depthTree(root->right)) + 1;
    }
};

二叉树的序列化

序列化与反序列化二叉树

剑指Offer 37, LC297 Serialize and Deserialize Binary Tree

序列化：用前序遍历来进行序列化，每次遇到空指针的时候，用$符号来占位。

反序列化：遍历序列化的字符串，也是用递归的方法，模拟前序遍历。只不过这会我们需要传递一个指针的指针。C++里用指针的指针不如用指针的引用方便。

string_view版本 2020.6.18

class Codec {
private:
    inline constexpr static const char DELIM    = ',';
    inline constexpr static const char NULLNODE = '$';

    
    string m_tree;

    void serializeImpl(TreeNode* root)
    {
        if(!root)
        {
            m_tree += NULLNODE;
            m_tree += DELIM;
            return;
        }

        m_tree += to_string(root->val);
        m_tree += DELIM;

        serializeImpl(root->left);
        serializeImpl(root->right);
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        serializeImpl(root);
        return m_tree;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string_view data) {
        auto first = data.begin();
        return deserialize(first, data.end());
    }

    template<typename It>
    TreeNode* deserialize(It& first, It last)
    {
        // check if it is a null node
        if(*first == NULLNODE)
        {
            first += 2;
            return nullptr;
        }

        // if it is not a null node, then it must has a value
        // decode and extract it value
        const auto val = [&]
        {
            auto start = first;
            while(*first != DELIM)
            {
                ++first;
            }
            
            auto val = int{};
            from_chars(&*start, &*first, val);
            return val;
        }();

        // move the first iterator one step further to skip
        // the delimiter
        ++first;

        // do this recursively on its left and right subtrees
        auto root = new TreeNode{val};
        root->left = deserialize(first, last);
        root->right = deserialize(first, last);

        return root;
    }
};

采用迭代器实现的版本

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    inline constexpr static char DELIMITER = ',';
    inline constexpr static char NULLMARK  = '$';
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // use preorder traversal sequence to serialize the tree
        // we have to mark the nullptrs with some special char
        string res{};
        serialize(root, res);
        return res;
    }

    // to avoid constructing too many some strings
    // we pass the ref of the string
    void serialize(TreeNode* root, string& res)
    {
        if(!root) 
        {
            res += NULLMARK;
            res += DELIMITER;
            return;
        }

        res += to_string(root->val);
        res += DELIMITER;
        serialize(root->left, res);
        serialize(root->right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        auto it = data.begin();
        return deserialize(it, data.end());
    }

    template<typename It>
    TreeNode* deserialize(It& it, It end)
    {
        // nothing to deserilize
        if(it == end) return nullptr;
        // get a part from the stirng.
        auto start = it;
        while(*it != DELIMITER) ++it;
        string str(start, it);
        // skip the delimiter
        ++it;

        // check if str is a nullptr
        if (*str.begin() == NULLMARK) return nullptr;
        // if it is not NULLMARK, then it must be an integer
        int val = stoi(str);
        // create a TreeNode
        auto root = new TreeNode{val};
        root->left = deserialize(it, end);
        root->right = deserialize(it, end);
        return root;
    }
};

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

2019年8月实现的code

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return string{};
        auto result = string{};
        function<void(TreeNode*)> serializeImpl;
        serializeImpl = [&serializeImpl, &result](TreeNode* root){
            result += to_string(root->val);
            result += ",";
            if(!root->left) result += "$,";
            else            serializeImpl(root->left);
            if(!root->right) result += "$,";
            else            serializeImpl(root->right);
        };
        serializeImpl(root);
        cout<<result<<endl;
        return result;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;
        auto it = data.begin();
        auto end = data.end();
        auto result = static_cast<TreeNode*>(nullptr);
        auto& root = result;
        function<void(TreeNode*&)> deserializeImpl;  
        deserializeImpl = [&it, &end, &deserializeImpl](TreeNode*& root){
            if(it == end) return;
            auto begin = it;            
            while(*it != ',') ++it;
                        
            if(*begin == '$'){
                root = nullptr;
                ++it;
                return;
            }else{ 
                root = new TreeNode{stoi(string(begin, it))};
                ++it; 
            }
            deserializeImpl(root->left);  
            deserializeImpl(root->right);  
        };
        deserializeImpl(root);
        return result;
    }
};

序列化与反序列化N叉树

LC428 序列化和反序列化 N 叉树

LC297 Serialize and Deserialize Binary Tree的升级版。区别在于每一个节点的孩子节点数目node->children.size()是不一定的。我们不但需要记录该节点的值，还需要记录该节点孩子的数目。同样采用前序遍历来序列化。再用前序遍历来反序列化。

code

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Codec {
private:
    inline constexpr static const char DELIM = ',';
    inline constexpr static const char NULLNODE = '$';
public:
    // Encodes a tree to a single string.
    string serialize(Node* root) {
        auto res = string{};
        serialize_impl(root, res);
        return res;
    }

    static void serialize_impl(Node* root, string& encode)
    {
        if(!root)
        {
            encode += NULLNODE;
            encode += DELIM;
            return;
        }

        // encode the value with the number of children.
        encode += to_string(root->val);
        encode += DELIM;
        encode += to_string(root->children.size());
        encode += DELIM;

        for(auto child : root->children)
        {
            serialize_impl(child, encode);
        }
    }
    
    // Decodes your encoded data to tree.
    Node* deserialize(string_view data) {
        auto first = data.begin();
        return deserialize(first, data.end());
    }

    template<typename It>
    static Node* deserialize(It& first, It last)
    {
        if(*first == NULLNODE)
        {
            first += 2;
            return nullptr;
        }

        auto read_int = [&]
        {
            auto val = int{};
            auto [delim, errc] = from_chars(&*first, &*last, val);
            first += (delim - &*first) + 1;
            return val;
        };

        // read twice, one for the value, one for the number of
        // children 
        const auto val = read_int();
        const auto children_num = read_int();

        auto root = new Node{val};
        for(auto i = size_t{}; i < children_num; ++i)
        {
            root->children.push_back(deserialize(first, last));
        }

        return root;
        
    }
};

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

重建二叉树

根据前序和中序遍历序列重建

剑指Offer 7, LC105 Construct Binary Tree from Preorder and Inorder Traversal

前序遍历序列中，根节点一定是第一个数字
中序遍历序列中，根节点位于中间，其左边是其左子树的中序遍历序列，右边是其右子树的中序遍历序列
思路：
找根节点：我们用前序遍历序列的第一个数字在中序遍历序列中的位置。同时我们也知道了左右子树节点的数量。
找左右子树的遍历前序遍历序列：根据左右子树节点的数量确认。
在其左右子树上递归的调用

code

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }

    template<typename It>
    TreeNode* buildTree(It first1, It last1, It first2, It last2)
    {
        if(!(first1 < last1) || !(first2 < last2)) return nullptr;

        // the first node must be the root of the tree in preoreder tra
        // find this in the inorder tra
        auto rootIt = find(first2, last2, *first1);

        // find the size of its left subtree
        auto leftTreeSize = rootIt - first2;

        // find the last It for its left subtree
        auto last1_left = first1 + leftTreeSize + 1;

        // create a node for root
        auto root = new TreeNode{*rootIt};
        root->left  = buildTree(first1 + 1, last1_left, first2, rootIt);
        root->right = buildTree(last1_left, last1, rootIt + 1, last2);
        return root;
    }
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preoder.empty() || inorder.empty())
        return buildTreeImpl(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());        
    }
    template<typename It>
    TreeNode* buildTreeImpl(It pbegin, It pend, It ibegin, It iend){
        
        if(pbegin == pend) return nullptr;
        
        auto proot = pbegin;
        auto iroot = find(ibegin, iend, *proot);
        auto leftTreeNumber = distance(ibegin, iroot);
        auto rightTreeNumber = distance(iroot,iend);
        
        auto leftpbegin = proot + 1;
        auto leftpend = leftpbegin + leftTreeNumber;     
        auto rightpbegin = leftpend;
        auto rightpend = pend;
        
        auto leftibegin = ibegin;
        auto leftiend = iroot;
        auto rightibegin = iroot + 1;
        auto rightiend = iend;
        
        auto leftChild  = buildTreeImpl(leftpbegin, leftpend, leftibegin, leftiend);
        auto rightChild = buildTreeImpl(rightpbegin, rightpend, rightibegin, rightiend);
        
        auto rootNode = new TreeNode{*proot};
        
        if(leftChild)  rootNode->left = leftChild;
        if(rightChild) rootNode->right = rightChild;
        
        return rootNode;
    }
};

根据后序和中序遍历序列重建

LC106 Construct Binary Tree from Inorder and Postorder Traversal
思路同上，不同点在于

后序遍历的根节点是最后一个

代码去掉了中间变量

code

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTree(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
    }
    template<typename It>
    TreeNode* buildTree(It first1, It last1, It first2, It last2)
    {
        // invariance last1 - first1 == last2 - first2

        // there is no node left in range, just return nullptr
        if(!(first1 < last2) || !(first2 < last2))
        {
            return nullptr;
        }
        // the root of the tree must be the last 
        // node of postorder traversal sequence
        --last2;
        // find this root in the inorder traversal sequence
        // it must seperate the inorder traversal sequence into its left
        // and right subtree
        auto rootIt = find(first1, last1, *last2);
        // compute the size of its right subtree
        auto rightTreeSize = last1  - (rootIt + 1);
        // compute the last It for its left subtree in the postorder
        // traversal sequence.
        auto last2_left = last2 - rightTreeSize;
        // create a new TreeNode for this root
        auto root = new TreeNode{*rootIt};

        root->left  = buildTree(first1, rootIt, first2, last2_left);
        root->right = buildTree(rootIt + 1, last1, last2_left, last2);

        return root;
    }
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTreeImpl(postorder.begin(), postorder.end(), inorder.begin(), inorder.end());
    }
    template<typename It>
    TreeNode* buildTreeImpl(It pbegin, It pend, It ibegin, It iend){
        if(pbegin == pend) return nullptr;
        auto proot = pend - 1;
        auto iroot = find(ibegin, iend, *proot);
        
        auto leftTreeNumber = distance(ibegin, iroot);
        auto rightTreeNumber = distance(iroot + 1, iend);
    
        auto rightChild = buildTreeImpl(proot - rightTreeNumber
                                      ,proot
                                      ,iroot + 1
                                      ,iend);
        auto leftChild = buildTreeImpl(pbegin
                                      ,pbegin + leftTreeNumber
                                      ,ibegin
                                      ,iroot);
        auto rootNode = new TreeNode{*proot};
        if(leftChild) rootNode->left = leftChild;
        if(rightChild) rootNode->right = rightChild;
        return rootNode;
    }
};

二叉树的路径

向下路径

向下路径可以被定义为：从根节点出发到任一节点的一条路径。
叶子路径：从根节点出发到叶子节点的一条路径。

一个节点的向下路径可以是：

仅包含该节点
包含该节点和其左子树的向下路径
包含该节点和其右子树的向下路径

一个节点的叶子路径是（注意：不可以仅仅包含该节点）

包含该节点和其左子树的向下路径
包含该节点和其右子树的向下路径

二叉树的深度（最大叶子路径长度）

剑指Offer 55, LC104 Maximum Depth of Binary Tree

思路一：
求二叉树的最大深度，就是求二叉树中最大的叶子路径长度。

空节点的最大叶子路径长度为0
一个节点的最大叶子路径长度是 1 + max(左子树的最大叶子路径长度，右子树的最大叶子路径长度)

思路二：
定义：空树的深度为0。则二叉树的最大深度 = max(左子树的最大深度, 右子树的最大深度) + 1。

code

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left), 
                   maxDepth(root->right)) + 1;
    }
};

二叉树的最小深度（最小叶子路径长度）

LC111 Minimum Depth of Binary Tree

思路一：
求二叉树的最小深度，就是求二叉树中最小的叶子路径长度。

一个节点的最小叶子路径长度是：

空节点的最小叶子路径长度为0
如果左右子树有一个为空，则为 1 + 左子树最小叶子路径长度 + 右子树最小叶子路径长度：
- 两个都为空，返回1
- 如果有一个为空，则返回 1 + 另一个
如果左子树都不为空，则为 1 + min(左子树最小叶子路径长度, 右子树最小叶子路径长度)

code

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;

        auto l = minDepth(root->left);
        auto r = minDepth(root->right);

        if(l == 0 || r == 0) return 1 + r + l;
        else return 1 + min(l ,r);
    }
};

思路二：
一个二叉树的最小深度等于

如果没有左孩子，是右子树的最小深度+1
如果没有右孩子，是左子树的最小深度+1
如果左右孩子都有，是左右孩子的最小深度当中较小的一个+1

code

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(root->left && !root->right)
        {
            return minDepth(root->left) + 1;
        }
        if(!root->left && root->right)
        {
            return minDepth(root->right) + 1;
        }
        return min(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        auto leftDepth = minDepth(root->left);
        auto rightDepth = minDepth(root->right);
        if(leftDepth == 0)  return 1 + rightDepth;
        if(rightDepth == 0) return 1 + leftDepth;
        return leftDepth < rightDepth ? leftDepth + 1 : rightDepth + 1;
    }
};

向下路径和

LC257 二叉树的所有路径
 LC112 路径总和
 LC113 路径总和II
LC437 路径总和III
LC129 根到叶子组成的数字

见回溯#二叉树的路径

LC120 三角形最小路径和

思路一(TLE)：
回溯暴力找，TLE在预期之内。

code

class Solution {
private:
    int level_end;
    int min_sum;
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty() || triangle.front().empty())
            return 0;
        level_end = triangle.size();
        min_sum = INT_MAX;
        backtrack(0, 0, 0, triangle);
        return min_sum;
    }

    void backtrack(int level, int idx, int sum, 
                    const vector<vector<int>>& triangle)
    {
        if(level == level_end)
        {
            min_sum = min(min_sum, sum);
            return;
        }

        for(int i = idx; i < idx + 2; ++i)
        {
            backtrack(level + 1, i, sum + triangle[level][idx], triangle);
        }
    }
};

思路二：
第l层中，第i个节点的最小路径和是：dp[l][i] = triangle[l][i] + min(dp[l + 1][i], dp[l + 1][i + 1])。可以看出这是一个动态规划问题。初始状态是当l为最后一层时，dp[l][i] = triangle[l][i]。从下到上填表即可。

code

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {

        if(triangle.empty() || triangle.front().empty()) return 0;

        for(auto it = ++triangle.rbegin(); it != triangle.rend(); ++it)
        {
            auto& level =  *it;
            const auto& next_level = *(it - 1);
            for(size_t i = 0; i < level.size(); ++i)
            {
                level[i] = level[i] + min(next_level[i], next_level[i + 1]);
            }
        }

        return triangle.front().front();
    }

};

折返路径

折返路径是一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

对于二叉树中的每一个节点，经过该节点的这种路径有四种（注意是向下路径，不是到达叶子节点的向下路径）

仅包含该节点
包含该节点和其左子树中的一条向下路径
包含该节点和其右子树中的一条向下路径
包含该节点和其左子树中的一条向下路径 和其右子树中的一条向下路径

可见，求折返路径的实质仍然是求向下路径。折返路径只不过是在每个节点，对其左右节点的向下路径的总结。因此大部分折返路径的问题，其递归函数的返回值仍然是向下路径的。

折返路径的长度

LC543 二叉树的直径

求二叉树中最长折返路径的长度 - 1。

思路1：遍历二叉树中所有节点，在每一个节点都计算一次其左子树和右子树的向下路径长度。二叉树的直径即是最大的【左子树向下路径 + 右子树向下路径】。

code

class Solution {
private:
    int m_res = 0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        diameter(root);
        return m_res;
    }

    void diameter(TreeNode* root)
    {
        if(!root)
        {
            return;
        }
        
        m_res = max
        (
            m_res,
            down_path_size(root->left) + down_path_size(root->right)
        );

        diameterOfBinaryTree(root->left);
        diameterOfBinaryTree(root->right);       
    }

    int down_path_size(TreeNode* root)
    {
        if(!root)
        {
            return 0;
        }

        return max(
            1 + down_path_size(root->left),
            1 + down_path_size(root->right));
    }
};

思路2：
直接计算根节点的向下路径长即可。因为想要得到一个节点的向下路径长度，必然需要先得到其左右的向下路径长度。如果其左右子树的向下路径长度已知，我们就可以顺便算出该节点的直径长度。

code

class Solution {
private:
    int res;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        res = 0;
        downPathLen(root);
        return res - 1;
    }

    int downPathLen(TreeNode* root)
    {
        if(!root) return 0;
        auto lDownPathLen = downPathLen(root->left);
        auto rDownPathLen = downPathLen(root->right);

        res = max(res, 1 + lDownPathLen + rDownPathLen);

        return 1 + max(lDownPathLen, rDownPathLen);
    }
};

最长同值折返路径

LC687 最长同值路径

思路一：
找树中的最长同值折返路径，就是找树中所有节点的最长同值折返路径。

一个节点的最长同值折返路径是：

初始化len = 1
如果他和左孩子相等，len = len + 左孩子的最长同值向下路径
如果他和右孩子相等，len = len + 右孩子的最长同值向下路径

一个节点的最长同值向下路径是：1 + max(左孩子的最长同值向下路径, 右孩子的最长同值向下路径)

code

class Solution {
private:
    int res;
public:
    int longestUnivaluePath(TreeNode* root) {
        res = 0;
        longestUnivaluePath__(root);
        return res;
    }

    void longestUnivaluePath__(TreeNode* root) {
        if(!root) return;
        longestUnivaluePath_(root);
        longestUnivaluePath__(root->left);
        longestUnivaluePath__(root->right);
    }

    int longestUnivaluePath_(TreeNode* root) {
       
        if(!root) return 0;

        auto left = 0;
        auto right = 0;

        if(root->left && root->val == root->left->val)
        {
            left = longestUnivaluePath_(root->left);
        }

        if(root->right && root->val == root->right->val)
        {
            right = longestUnivaluePath_(root->right);
        }

        res = max(res, left + right);

        return 1 + max(left, right);
    }
};

思路二：

在思路一种我们用了递归套递归来完成计算，导致了大量的重复。我们思考修改程序的结构，只用一种递归来完成。
思路一中，计算向下路径的流程判断root->left && root->val == root->left->val和root->right && root->val == root->right->val阻断递归函数的向下传播，导致我们必须使用另一个递归函数来遍历所有树的节点。

之前提到过，折返路径的本质仍然是向下路径。折返路径只不过是在每个节点，对其左右节点的向下路径的总结。所以我们先想出最长向下同值路径该怎么写？然后再在其中添加上计算折返路径的程序段即可。可以观察到，下面的代码如果去掉求折返路径的程序段，就会变成一个求向下路径的递归函数。

code

class Solution {
private:
    int res;
public:
    int longestUnivaluePath(TreeNode* root) {
        res = 0;
        lup(root);
        return res;
    }

    int lup(TreeNode* root) {

        if(!root) return 0;

        auto left = lup(root->left);
        auto right = lup(root->right);

        /* 求折返路径的程序段 */
        auto cur_path = 0;
        /* 求折返路径的程序段 */

        auto cur = 1;

        if(root->left && root->val == root->left->val)
        {
            cur = max(cur, 1 + left);
            /* 求折返路径的程序段 */
            cur_path += left;
            /* 求折返路径的程序段 */
        }

        if(root->right && root->val == root->right->val)
        {
            cur = max(cur, 1 + right);
            /* 求折返路径的程序段 */
            cur_path += right;
            /* 求折返路径的程序段 */
        }

        /* 求折返路径的程序段 */
        res = max(res, cur_path);
        /* 求折返路径的程序段 */

        return cur;
    }

};

折返路径和

LC124 Binary Tree Maximum Path Sum

求二叉树中折返路径的最大路径和。思路类似动态规划中最大子数组和。

思路：要求所有折返路径的最大路径和，我们需要求通过每一个节点的折返路径的路径和的最大值。在求一个节点的折返路径和之前，我们需要知道其左子树的向下路径的路径和和其右子树的向下路径的路径和。因此考虑后续遍历（或者说是自然就写成了后续遍历）。

如果该节点为空节点，不存在折返路径，向下路径和为0。
该节点的折返路径和为该节点的值 + max(左子树向下路径和最大值, 0) + max(右子树向下路径和最大值, 0)。因为折返路径可以是：
- 仅包含该节点，即max(左子树向下路径和最大值, 0) = 0，且 max(右子树向下路径和最大值, 0) = 0。
- 包含该节点和左子树的向下路径，即max(左子树向下路径和最大值, 0) 不等于 0，但max(右子树向下路径和最大值, 0) = 0
- 包含该节点和右子树的向下路径，同理
- 包含该节点和左右子树的向下路径，即max(左子树向下路径和最大值, 0) 不等于 0 且 max(右子树向下路径和最大值, 0) 不等于 0
- 折返路径不可以不包含该节点，因为定义中要求：该路径至少包含一个节点。
该节点的向下路径和为该节点的值 + max(左子树向下路径和最大值, 右子树向下路径和最大值)。

code

class Solution {
private:
    int res;
public:
    int maxPathSum(TreeNode* root) {
        res = INT_MIN;
        downPathSum(root);
        return res;
    }

    int downPathSum(TreeNode* root)
    {
        if(!root) return 0;

        auto lDownPathSum = downPathSum(root->left);
        auto rDownPathSum = downPathSum(root->right);

        res = max(res, root->val + max(lDownPathSum, 0) + max(rDownPathSum, 0));

        return root->val + max({0, lDownPathSum, rDownPathSum});
    }
};

平衡二叉树

剑指Offer 55, LC110 平衡二叉树

判断一个二叉树是否满足以下性质：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

思路一：

类似求折返路径的思路。

递归函数求每个节点的叶子路径长度。
检查该节点的左孩子和右孩子的叶子路径长度差是否超过1。

code

class Solution {
private:
    bool res;
public:
    bool isBalanced(TreeNode* root) {
        res = true;
        depth(root);
        return res;
    }

    int depth(TreeNode* root)
    {
        if(!root) return 0;

        auto left = depth(root->left);
        auto right = depth(root->right);

        if(left - right > 1 || right - left > 1)
        {
            res = res && false;
        }

        return max(1 + left, 1 + right);
    }
};

两个二叉树的关系

相同的树

LC100 相同的树

思路：设计程序同时遍历两个树。当一个指针是空指针时，也要求另一个指针也是空指针。之后检查值是否相等就可以。不传引用的版本要明显快一些。

不传引用的版本

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

        return isSameTree(p->left, q->left)
            && isSameTree(p->right,q->right);
    }
};

传引用的版本

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        bool res = true;
        isSameTree(p, q, res);
        return res;
    }

    void isSameTree(TreeNode* p, TreeNode* q, bool& res)
    {
        if(!res) return;
        if((p == nullptr) ^ (q == nullptr)) {res = false;return;}
        if(!p && !q) return;

        if (p->val != q->val) {res = false; return;}
        isSameTree(p->left, q->left, res);
        isSameTree(p->right,q->right,res);
    }
};

树的子结构

剑指Offer 26, [Acwing37 树的子结构]（https://www.acwing.com/problem/content/description/35/ ）
LC面试题26. 树的子结构

前一题相同的树的升级版。我们只需要遍历A树，找到和B树根节点的值相同的节点，然后在这里开始判断两个树是否相同。
注意：

- 判例认为空树不是任何树的子树
- 不能简单的复制前一题的isSameTree。因为**A树指针不为空，而B树指针为空**这种情况是允许的。但是不能**A为空，B不为空**。

recursive code

class Solution {
private:
    bool res;
    TreeNode* A;
    TreeNode* B;
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A && !B) return true;
        if((A && !B) || (!A && B)) return false;
        this->A = A;
        this->B = B;
        res = false;
        dfs(A);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if(res || !root) return;

        if(root->val == B->val)
        {
            res = res || unguarded_isSameTree(root, B);
        }

        dfs(root->left);
        dfs(root->right);
    }

    bool unguarded_isSameTree(TreeNode* A, TreeNode* B)
    {
        if(!A && B) return false;
        if( (!B && A) || (!A && !B) ) return true;
        if(A->val != B->val) return false;

        return unguarded_isSameTree(A->left, B->left)  &&
               unguarded_isSameTree(A->right, B->right);
    }
};

stack code

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!B) return false;
        vector<TreeNode*> stack{};
        // do a preorder traversal
        while(true)
        {
            while(A)
            {
                // if we find nodes have the same value, check from there
                if(A->val == B->val 
                    && unguarded_isSameTree(A, B))
                    goto found;
                stack.push_back(A->right);
                A = A->left;
            }
            if(stack.empty()) break;
            A = stack.back();
            stack.pop_back();
        }
        return false;
    found:
        return true;
    }

    bool unguarded_isSameTree(TreeNode* p, TreeNode* q)
    {
        if(!p && !q) return true;
        if(!q && p) return true;
        if(!p && q) return false;
        if(p->val != q->val) return false;
        return unguarded_isSameTree(p->left, q->left) &&
               unguarded_isSameTree(p->right, q->right);
    }
};

2019年8月的思路和code

被搜索的树叫s,另一个叫t
思路：

首先遍历第一个树，找到和第二个树根节点值相同的节点。
从这里开始遍历两个树。
- 如果t == nullptr，返回true，不需要管s是不是空。
- 如果t != nullptr && s == nullptr返回false
- 如果t和s节点的值不同，返回false
- 继续搜索左子树和右子树。return 左 && 右。

注意：这个题的判例会很奇怪的认为空的树不是另一个树的子树。

class Solution {
public:
    Solution()
    :result(false)
    ,t(nullptr)
    {}
    
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        result = false;
        if(!pRoot2) return false;
        if(!pRoot1) return false;
        t = pRoot2;
        hasSubtreeImpl1(pRoot1);
        return result;
    }
private:
    bool result;
    TreeNode* t;
    
    void hasSubtreeImpl1(TreeNode* s){
        if(s->val == t->val)    result = hasSubtreeImpl2(s, t);
        if(!result && s->left)  hasSubtreeImpl1(s->left);
        if(!result && s->right) hasSubtreeImpl1(s->right);
    }
    
    bool hasSubtreeImpl2(TreeNode* s, TreeNode* t){
        if(!t) return true;
        if(!s) return false;
        if(!(s->val == t->val)) return false;
        return hasSubtreeImpl2(s->left, t->left) && hasSubtreeImpl2(s->right, t->right);
    }

};

LC572 Subtree of Another Tree
LC面试题04.10 检查子树
这个题和剑指Offer 26的题不同，这个题要求【子结构】不能是原来的树的一部分，必须从根节点开始，所有子节点一模一样，不能多，也不能少。修改一下判断是否相同的函数就可以了

2020.6.20 code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool checkSubTree(TreeNode* t1, TreeNode* t2) {
        
        if(!t1 && !t2)
        {
            return true;
        }
        
        if(!t1 && t2)
        {
            return false;
        }

        if(t1->val == t2->val)
        {
            return is_same_tree(t1, t2);
        }

        return checkSubTree(t1->left, t2) || checkSubTree(t1->right, t2); 
    }

    bool is_same_tree(TreeNode* r1, TreeNode* r2)
    {
        if(!r1 && !r2)
        {
            return true;
        }
        
        if((!r1 && r2) || (r1 && !r2)
        || (r1->val != r2->val))
        {
            return false;
        }

        return is_same_tree(r1->left, r2->left) && is_same_tree(r1->right, r2->right);
    }
};

2020.6.18 code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    bool res = false;
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        isSubtree_impl(s, t);
        return res;
    }

    void isSubtree_impl(TreeNode* s, TreeNode* t)
    {   
        if(res || !s)
        {
            return;
        }

        if(s->val == t->val)
        {
            res = is_same_tree(s, t);
        }

        if(!res)
        {
            isSubtree_impl(s->left, t);
            isSubtree_impl(s->right, t);
        }
    }

    auto is_same_tree(TreeNode* s, TreeNode* t) -> bool
    {
        if((!s && !t))
        {
            return true;
        }

        if((!s && t) || (!t && s)
        || (s->val != t->val))
        {
            return false;
        }

        return is_same_tree(s->left , t->left) 
        &&     is_same_tree(s->right, t->right);
    }
};

code

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!t) return true;
        if(!s) return false;
        auto result = false;
        function<void(TreeNode*)> isSubTreeImpl1;
        function<bool(TreeNode*, TreeNode*)> isSubTreeImpl2;
        
        isSubTreeImpl1 = [&isSubTreeImpl1, &isSubTreeImpl2, &result, t](TreeNode* root){
            if(root->val == t->val){result = isSubTreeImpl2(root, t);}
            if(!result && root->left)  isSubTreeImpl1(root->left);
            if(!result && root->right) isSubTreeImpl1(root->right);
        };
        
        isSubTreeImpl2 = [&isSubTreeImpl2](TreeNode* s, TreeNode* t){
            if(!t && !s) return true;//修改这里！
            if(!t || !s) return false;//修改这里！
            if(s->val != t->val) return false;
            return isSubTreeImpl2(s->left, t->left) && isSubTreeImpl2(s->right, t->right);
        };
        
        isSubTreeImpl1(s);
        
        return result;
    }  
};

合并二叉树

LC617 合并二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // both of them are nullptr, nothing to do
        if(!t1 && !t2) return nullptr;
        // if one of them is a nullptr, the value of the new
        // node will be the one that is not nullptr
        int val = 0;
        if(t1 && !t2)
        {
            val = t1->val;
        }
        else if(!t1 && t2)
        {
            val = t2->val;
        }
        else // (t1 && t2)
        {
            val = t1->val + t2->val;
        }

        // create a new node
        TreeNode* root = new TreeNode{val};
        // recursively call and create
        
        root->left = mergeTrees(leftNode(t1),leftNode(t2));
        root->right = mergeTrees(rightNode(t1), rightNode(t2));

        return root;
    }

    static inline TreeNode* leftNode(TreeNode* root)
    {
        return root ? root->left : nullptr;
    }

    static inline TreeNode* rightNode(TreeNode* root)
    {
        return root ? root->right : nullptr;
    }
};

对称的二叉树

求一个二叉树的镜像：

剑指Offer 27, LC226 Invert Binary Tree
homebrew作者写不出来的代码。遍历过程中交换二叉树的左孩子和右孩子指针即可。

code

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        swap(root->left, root->right);
        root->left = invertTree(root->left);
        root->right = invertTree(root->right);
        return root;
    }
};

判断两个树为镜像(判断一个树对称)：

剑指Offer 28, LC101 Symmertic Tree

使用我们在迭代后序遍历二叉树时的技巧：对称的前序遍历。如果一棵树的对称前序遍历和前序遍历相同，那么这棵树是对称的。

code

class Solution {
private:
    bool res;
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        res = true;
        isSymmetric(root, root);
        return res;
    }

    void isSymmetric(TreeNode* A, TreeNode* B)
    {
        if(!res || (!A && !B)) return;
        if((!A && B) || (!B && A) || (A->val != B->val))
        {
            res = false;
            return;
        }

        isSymmetric(A->left, B->right);
        isSymmetric(A->right, B->left);
    }
};

树中两个节点的最低公共祖先

二叉搜索树的最低公共祖先

LC235 Lowest Common Ancestor of a Binary Search Tree

如果当前节点比两个节点的值都小，搜索当前节点的右子树。
如果当前节点比两个节点的值都大，搜索当前节点的左子树。
如果当前节点在两个节点确定的闭区间中，返回当前节点。

（如果保证BST里没有重复节点可以这么写，如果BST里有重复节点，那就很麻烦了）

code

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        
        while(root){
            if(root->val < p->val && root->val < q->val) root = root->right;
            if(p->val < root->val && q->val < root->val) root = root->left;
            else break; 
        }
        return root;
    }
};

二叉树的最低公共祖先

LC236 Lowest Common Ancestor of a Binary Tree

不像二叉搜索树一样，节点的值之间有一定的规律。在向下路径当中我们曾经提到：从根节点到树中某一节点的向下路径是唯一的。我们需要找到从根节点到两个节点的向下路径。之后在其中找都首个不匹配的元素，其公共祖先即为首个不匹配的元素前一个元素。如果不存在不匹配的元素，说明这两个节点是完全一样的。首个不匹配的元素前一个元素即为该节点，符合题目要求。

code

class Solution {
private:
    vector<TreeNode*> cur_path;
    vector<TreeNode*> p_path;
    vector<TreeNode*> q_path;
    TreeNode* p;
    TreeNode* q;
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p == q) return p;
        this->p = p;
        this->q = q;

        backtrack(root);

        auto [it1, it2] = mismatch(p_path.begin(), p_path.end(), q_path.begin());

        return *(--it1);
    }

    void backtrack(TreeNode* root)
    {
        if(!root) return;

        cur_path.push_back(root);

        if(root == p)
        {
            p_path = cur_path;
        }
        else if(root == q)
        {
            q_path = cur_path;
        }

        backtrack(root->left);
        backtrack(root->right);

        cur_path.pop_back();
    }
};

二叉树的最近叶节点

LC742 二叉树的最近叶节点

一个节点A到另一个节点B的距离，即是A到B的路径的长度。为了求路径的长度，我们需要找到折返点。注意到根节点到任何节点的向下路径是唯一的。因此：

找到根节点到A和B的向下路径
用std::mismatch找到首个在A和B中的向下路径中不匹配的位置pa, pb
计算pa到A向下路径末尾的长度+pb到B向下路径末尾的长度，其和即为路径长度。

思路：

遍历二叉树，记录下目标节点和所有叶子节点的向下路径。
计算目标节点到所有叶子节点的距离。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    unordered_map<TreeNode*, vector<TreeNode*>> m_path_map = {};
    vector<TreeNode*> m_path = {};
    int m_target = 0;
    TreeNode* m_target_node = nullptr;
    size_t m_min_dist = UINT32_MAX;
    int m_res = 0;
public:
    int findClosestLeaf(TreeNode* root, int k) {
        m_target = k;
        build_path(root);
        closest_leaf();
        return m_res;
    }

    void build_path(TreeNode* root)
    {
        if(!root)
        {
            return;
        }

        m_path.push_back(root);

        if((!root->left && !root->right)
        || root->val == m_target)
        {
            m_path_map[root] = m_path;
            if(root->val == m_target)
            {
                m_target_node = root;
            }
        }

        build_path(root->left);
        build_path(root->right);
        
        m_path.pop_back();
    }

    void closest_leaf()
    {
        for(const auto& p : m_path_map)
        {
            if(p.first->val != m_target)
            {
                if(auto dist = distance(m_target_node, p.first);
                    m_min_dist > dist)
                {
                    m_res = p.first->val;
                    m_min_dist = dist;
                }
            }
            else if(!p.first->left && !p.first->right)
            {
                m_min_dist = 0;
                m_res = p.first->val;
            }
        }
    }

    size_t distance(TreeNode* lhs, TreeNode* rhs)
    {
        const auto& lpath = m_path_map[lhs];
        const auto& rpath = m_path_map[rhs];

        auto [lp, rp] = mismatch(lpath.begin(), lpath.end(), rpath.begin(), rpath.end());
        
        return (lpath.end() - lp) + (rpath.end() - rp);
    }
};

完全二叉树的节点个数

见二分查找#困难二分查找##完全二叉树的节点个数

二叉树的边界

LC545 二叉树的边界

左边界和右边界的定义比较复杂：

在左子树存在时总是优先访问，如果不存在左子树则访问右子树。重复以上操作，首先抵达的结点就是最左侧结点。
左边界的定义是从根到最左侧结点的路径。
若根没有左子树，则根自身就是左边界。

找出左边界，右边界和下边界（即所有叶子结点）后，由于左边界和右边界中可能包含有叶子结点，因此会出现重复节点。去掉这些重复节点即可。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<TreeNode*> m_leftpath;
    deque<TreeNode*> m_rightpath;
    vector<TreeNode*> m_bottompath;
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if(!root)
        {
            return {};
        }
        [=]()mutable
        {
            m_leftpath.push_back(root);
            root = root->left;
            while(root)
            {
                m_leftpath.push_back(root);
                if(root->left)
                {
                    root = root->left;
                }
                else if(root->right)
                {
                    root = root->right;
                }
                else
                {
                    break;
                }
            }
        }();

        [=]()mutable
        {
            root = root->right;
            while(root)
            {
                m_rightpath.push_front(root);
                if(root->right)
                {
                    root = root->right;
                }
                else if(root->left)
                {
                    root = root->left;
                }
                else
                {
                    break;
                }
            }
        }();

        preorder(root);

        // clean duplicate nodes
        if(m_leftpath.back() == m_bottompath.front())
        {
            m_leftpath.pop_back();
        }

        if(m_bottompath.back() == m_rightpath.front())
        {
            m_bottompath.pop_back();
        }

        // build the result

        auto res = vector<int>{};
        auto tsfm = [](auto x)
        {
            return x->val;
        };
        transform(m_leftpath.begin(), m_leftpath.end(), back_inserter(res), tsfm);
        transform(m_bottompath.begin(), m_bottompath.end(), back_inserter(res), tsfm);
        transform(m_rightpath.begin(), m_rightpath.end(), back_inserter(res), tsfm);

        return res;
    }
    
    void preorder(TreeNode* root)
    {
        if(!root)
        {
            return;
        }

        if(!root->left && !root->right)
        {
            m_bottompath.push_back(root);
        }

        preorder(root->left);
        preorder(root->right);
    }
};

二叉树展开为链表

LC114 二叉树展开为链表

使用栈辅助的前序遍历。不断地将之前的节点的右孩子设置为当前节点，并将左孩子设置为nullptr

code

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* pre = nullptr;
        auto s = stack<TreeNode*>{};
        auto r = vector<int>{};
        while(true)
        {
          while(root)
          {
            s.push(root->right);
            // visit 
            if(!pre)
            {
              pre = root;
            }else
            {
              pre->right = root;
              pre->left = nullptr;
              pre = root;
            }
            root = root->left;
          }

          if(s.empty())
          {
            break;
          }

          root = s.top();
          s.pop();
        }
    }
};

子树

分裂子树的最大乘积

去掉一条边，将一棵树分成两颗树。其中一棵树以该边的子节点为根节点，很容易获得其节点和。为了得到另一棵树的节点和，我们需要先知道整个树的节点和，用整个树的节点和减去一边的节点和，即是另一边的节点和。

统计所有子树的节点和。
根据均值不等式，找到和【整个树节点和】S一半最接近的节点和T。
所求结果即为S * (S - T)

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    set<int64_t> m_sum = {};
public:
    int maxProduct(TreeNode* root) {
        auto sum = tree_sum(root);
        auto m1 = *min_element(m_sum.begin(), m_sum.end(), [a = sum / 2.](auto lhs, auto rhs)
        {
            return abs(a - lhs) < abs(a - rhs);
        });
        return (m1 * (sum - m1)) % 1000000007;
    }

    int64_t tree_sum(TreeNode* root)
    { 
        if(!root)
        {
            return 0;
        }
        auto sum = root->val + tree_sum(root->left) + tree_sum(root->right);
        m_sum.insert(sum);
        return sum;
    }
};

统计同值子树

LC250 统计同值子树

一个树如果所有节点的值都相等，那么称其为同值
空树一定是同值的，没有孩子的树一定是同值的
如果一个树的根节点满足下面所有条件，那么这颗树是同值的
- 左子树是同值的，右子树也是同值的
- 根节点的值等于左孩子的值，也等于右孩子的值
那么一个树的根节点满足下面任意条件，则不是同值的
- 左子树或右子树不是同值
- 根节点的值不等于左孩子的值或根节点的值不等于右孩子的值

要求统计所有同值子树的个数。我们遍历所有节点，在所有节点处都判断以该节点为根的树是否为同值子树。记录同值子树的个数。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int m_res = 0;
public:
    int countUnivalSubtrees(TreeNode* root) {
        countUnivalSubtrees_impl(root);
        return m_res;
    }

    void countUnivalSubtrees_impl(TreeNode* root)
    {
        if(!root)
        {
            return;
        }

        m_res += is_unival_tree(root);
        countUnivalSubtrees(root->left);
        countUnivalSubtrees(root->right);
    }

    bool is_unival_tree(TreeNode* root)
    {
        if(!root)
        {
            return true;
        }

        if((root->left && root->left->val != root->val)
        || (root->right && root->right->val != root->val))
        {
            return false;
        }

        return is_unival_tree(root->left) && is_unival_tree(root->right);
    }
};

改进：采用备忘录方式记录已经遍历过的节点是否为同值子树。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int m_res = 0;
    unordered_map<TreeNode*, bool> m_memo = {};
public:
    int countUnivalSubtrees(TreeNode* root) {
        countUnivalSubtrees_impl(root);
        return m_res;
    }

    void countUnivalSubtrees_impl(TreeNode* root)
    {
        if(!root)
        {
            return;
        }

        auto is_unival = is_unival_tree(root);
        m_memo[root] = is_unival;
        m_res += is_unival;

        countUnivalSubtrees(root->left);
        countUnivalSubtrees(root->right);
    }

    bool is_unival_tree(TreeNode* root)
    {
        if(!root)
        {
            return true;
        }

        if((root->left && root->left->val != root->val)
        || (root->right && root->right->val != root->val))
        {
            return false;
        }

        return is_unival_tree_memo(root->left) &&
        is_unival_tree_memo(root->right);
    }

    auto is_unival_tree_memo(TreeNode* root) -> bool
    {
        if(auto it = m_memo.find(root);
        it == m_memo.end())
        {
            auto res = is_unival_tree(root);
            m_memo[root] = res;
            return res;
        }
        else
        {
            return it->second;
        }
    }
};

子树的最大平均值

平均值 = 所有节点的值的和 / 节点数
一棵树的平均值 = (根节点的值 + 左子树的节点和 + 右子树的节点和) / (1 + 左子树的节点数 + 右子树的节点数)
递归地在所有节点计算即可。也可采用备忘录记录已经算过的节点。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    double m_res = 0.;
public:
    double maximumAverageSubtree(TreeNode* root) {
        maximumAverageSubtree_impl(root);
        return m_res;
    }

    void maximumAverageSubtree_impl(TreeNode* root)
    {
        if(!root) return;
        auto [s, n] = sum_and_num(root);
        m_res = max(m_res, s / static_cast<double>(n));
        maximumAverageSubtree_impl(root->left);
        maximumAverageSubtree_impl(root->right);
    }

    auto sum_and_num(TreeNode* root) -> std::pair<int, int>
    {
        if(!root)
        {
            return make_pair(0, 0);
        }

        auto [ls, ln] = sum_and_num(root->left);
        auto [rs, rn] = sum_and_num(root->right);

        return make_pair
        (
            ls + rs + root->val,
            ln + rn + 1
        );
    }
};

在二叉树中分配硬币

LC979 在二叉树中分配硬币

对于一个叶子节点：
- 如果硬币数为0，必然通过父节点得到一枚硬币
- 如果硬币数大于1，必须通过父节点转移一枚硬币
记一个子树的硬币不平衡数为b
- 空树的不平衡数为0
- 非空树的不平衡数为：左子树的不平衡数 + 右子树的不平衡数 + (该树根节点的硬币数 - 1)
通过该节点转移的硬币数为：|左子树的不平衡数| + |右子树的不平衡数|

我们需要统计通过所有节点转移的硬币数。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int m_total_transfered = 0;
public:
    int distributeCoins(TreeNode* root) {
        unbalance_coins(root);
        return m_total_transfered;
    }

    int unbalance_coins(TreeNode* root)
    {
        if(!root){
            return 0;
        }

        auto lu = unbalance_coins(root->left);
        auto ru = unbalance_coins(root->right);

        m_total_transfered += abs(lu) + abs(ru);

        return lu + ru + root->val - 1;
    }
};