Abstract

遍历 
// 144. 二叉树的前序遍历
vector<int> preorderTraversal(TreeNode* root);
// 94. 二叉树的中序遍历
vector<int> inorderTraversal(TreeNode* root);
// 145. 二叉树的后序遍历
vector<int> postorderTraversal(TreeNode* root);
// 102. 二叉树的层序遍历
vector<vector<int>> levelOrder(TreeNode* root);
// 111. 二叉树的最小深度 -- BFS 求最短路
int minDepth(TreeNode* root);
// 104. 二叉树的最大深度 -- DFS、bottom_up、 top_dowm
int maxDepth(TreeNode* root);
// 543. 二叉树的直径 -- 每个节点 左右子树最大深度 + 自身 构成一条路径，dfs用于求最大深度。
int diameterOfBinaryTree(TreeNode* root);
// 112. 路径总和 -- DFS, 叶子结点判断法，避免单叉结点匹配。
bool hasPathSum(TreeNode* root, int targetSum);
// 113. 路径总和 II - DFS path.emplace_back(node->val); path.pop_back();
vector<vector<int>> pathSum(TreeNode* root, int targetSum);
// 124. 二叉树中的最大路径和
int maxPathSum(TreeNode* root);

重新构造
// 105. 从前序与中序遍历序列构造二叉树, pre确定根节点的值，inorder确定左右子树，先左子树后左子树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)；
// 106.从中序与后序遍历序列构造二叉树, post确定根节点的值，inorder确定左右子树，先右子树后左子树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder);
// 297.二叉树序列化/反序列化
// 654.最大二叉树 构建

常见例题
// 226. 翻转二叉树 dfs先序、后序位置效果是一样的
TreeNode* invertTree(TreeNode* root);
// 114. 二叉树展开为链表, 右子树 接到更新后树的最右端
void flatten(TreeNode* root);
// 116. 填充每个节点的下一个右侧节点指针, 完美二叉树,递归出口&&
Node* connect_116(Node* root);
// 117. 填充每个节点的下一个右侧节点指针II, 一般二叉树, 递归出口||
Node* connect_117(Node* root);
// 101. 对称二叉树 -- 给你一个二叉树的根节点 root ， 检查它是否轴对称。
isSymmetric(TreeNode* root);

bool dfs_hasPathSum(TreeNode* node, int targetSum) {
  // 空节点退出
  if (node == nullptr) {
    return false;
  }
  // 叶子结点判断法
  if (node->left == nullptr && node->right == nullptr) {
    return targetSum == node->val;
  }
  bool left_has = dfs_hasPathSum(node->left, targetSum - node->val);
  bool right_has = dfs_hasPathSum(node->right, targetSum - node->val);
  return left_has || right_has;
}

树的问题，就是遍历所有节点找出一个答案喽。拿到问题，先考虑-深度优先？广度优先；然后再考虑用递归？迭代。

二叉树的最大深度： 一道题带你理解什么是自顶向上/自底向上–二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

树递归框架的小结：
自顶向上：需要使用一些参数和节点本身的值来决定传递给子节点参数
自底向上：如果知道子节点的答案就能知道该节点的答案，采用自底向上是个不错的选择

自底向上/自顶向上-都是深度优先递归，想要用深度优先迭代解需要将节点的层级状态存下来。
如果使用广度优先-无论是迭代，还是递归。res list 的层数就是最大深度。

路径总和 是一条从根结点->叶子结点 完整的路径， 路径和 两端可以是两个叶子结点，不需要经过根节点。

Introduction

二叉树节点结构：

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

树结构定义：一个节点，包含一个值和一个指向其他节点的列表。
树的定义天然带有递归的属性，树的许多问题可以通过递归的方式来解决。
对于每一个递归层级，我们只需要关注单个节点内的问题，然后通过递归调用来解决其子节点问题。

二叉树是一种典型的树状结构，每个节点最多有两个子树的树，通常被称作“左子树”和“右子树”。
二叉树用来存储具有树结构的数据，我们通过访问树的各个结点来进行数据处理。
【广度优先-Breadth First Search-BFS】可以逐层访问树节点，又叫层次遍历。
【深度优先-Depth First Search-DFS】也可以逐条路径(每一个可能的分支路径深入到不能再深入为止)访问结点。深度优先 按照根节点被访问到的顺序，又可分为：【先序遍历】、【中序遍历】、【后序遍历】。

广度优先/深度优先 遍历都各自拥有 迭代 和 递归 两种代码实现方式
【迭代】：找一种容器【队列/堆栈】存放暂时未访问到的节点，等到访问它了再把它弹出来。迭代退出条件是：容器是空的，即没有未被访问过的结点，即所有节点都被访问过了。
【递归】：需要存在递归函数和原函数，原函数中开启递归入口，递归函数不断递归求解。递归退出条件-如果节点为空，无需再往下递归。

二叉树常见的问题（遍历二叉树能够做啥）：
二叉树的最大深度：理解【自顶向上】、【自底向上】递归的经典例子。
对称二叉树：
路径综总和：

先序位置：自顶向下 翻转二叉树，二叉树的下一个节点
后序位置：自底向上 二叉树转链表， 二叉树的直径

1. 遍历

DFS - 深度优先 - 先序、中序、后序

深度优先 按照根节点被访问到的顺序可分为：【先序遍历】、【中序遍历】、【后序遍历】。

【递归】：需要存在递归函数和原函数，原函数中开启递归入口，递归函数不断递归求解。递归退出条件-如果节点为空，无需再往下递归。

// c++ 递归
class Solution {
    vector<int> _res;
public:
	// 144. 二叉树的前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        preorder_dfs(root);
        return _res;
    }
    void preorder_dfs(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        _res.push_back(node->val);
        preorder_dfs(node->left);
        preorder_dfs(node->right);
    }
    // 94. 二叉树的中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        inorder_dfs(root);
        return _res;
    }
    void inorder_dfs(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        inorder_dfs(node->left);
        _res.push_back(node->val);
        inorder_dfs(node->right);
    }
    // 145. 二叉树的后序遍历
    vector<int> postorderTraversal(TreeNode* root) {
        postorder_dfs(root);
        return _res;
    }
    void postorder_dfs(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        postorder_dfs(node->left);
        postorder_dfs(node->right);
        _res.push_back(node->val);
    }
};

# python 递归
def Solution():
    def __init__(self):
        self.max_h = 0
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        @note res 定义为函数作用域
        """
        res = []
        def preorder_dfs(root: TreeNode):
            if root == None:
                return
            res.append(root.val)
            preorder_dfs(root.left)
            preorder_dfs(root.right)
        preorder_dfs(root)
        return res

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        @note inorder 左中右
        """
        res = []
        def inorder_dfs(root: TreeNode):
            if root == None:
                return
            inorder_dfs(root.left)
            res.append(root.val)
            inorder_dfs(root.right)
        inorder_dfs(root)
        return res

    def postOrderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        @note post order 左右中 中右左的逆序
              直接递归 左右中会有什么问题？
        """
        res = []
        def postorder_dfs(root: TreeNode):
            if root == None:
                return 
            postorder_dfs(root.left)
            postorder_dfs(root.right)
            res.append(root.val)
        postorder_dfs(root)
        return res

【迭代】：找一种容器【堆栈】存放暂时未访问到的节点，等到访问它了再把它弹出来。迭代退出条件是：容器是空的，即没有未被访问过的结点，即所有节点都被访问过了。

前序迭代的框架：当前节点的右子树放入堆栈存起来。将当前节点的值放入res，当前节点更新为当前节点的左子树节点。

中序迭代框架：需要将什么放stack中呢，根节点一路向左遍历到底部。将根节点都放进去，放进去的就是有的节点。遍历到底端之后，逐个弹出；然后去该节点的右子树，如果右子树为空，就会弹该节点的父亲节点；如果右子树不为空，就可以迭代进去处理右子树。

后序迭代框架：中右左的逆序，就是左右中。在伪前序遍历（保存左节点）的结果下，逆序输出即可。

// c++迭代
class Solution {
public:
	// 144. 二叉树的前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> node_stack;
        TreeNode* node = root;
        while(!node_stack.empty() || node != nullptr) {
            if (node != nullptr) {
                res.push_back(node->val);
                node_stack.push(node->right);
                node = node->left;
            } else {
                node = node_stack.top();
                node_stack.pop();
            }
        }
        return res;
    }
    // 94. 二叉树的中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> node_stack;
        TreeNode* node = root;
        while(!node_stack.empty() || node != nullptr) {
            if (node != nullptr) {
                node_stack.push(node);
                node = node->left;
            } else {
                node = node_stack.top();
                node_stack.pop();
                res.push_back(node->val);
                node = node->right;
            }
        }
        return res;
    }
    // 145. 二叉树的后序遍历
    vector<int> postorderTraversal(TreeNode* root) {
        // 左右中 -> 中右左逆序
        vector<int> res;
        stack<TreeNode*> node_stack;
        TreeNode* node = root;
        TreeNode* pre_node = nullptr;
        while(!node_stack.empty() || node != nullptr) {
            if (node != nullptr) {
                res.push_back(node->val);
                node_stack.push(node->left);
                node = node->right;
            } else {
                node = node_stack.top();
                node_stack.pop();
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

# python 迭代
class Solution(object):
    def preorderTraversal(self, root):
        stack=[]
        res=[]
        node=root
        while(node or stack):
            if node:
                res.append(node.val)
                if node.right:
                    stack.append(node.right)
                node=node.left
            else:
                node=stack.pop()
        return res
    
    def inorderTraversal(self, root):
        stack=[]
        res=[]
        node=root
        while(stack or node):
            if node:
                stack.append(node)
                node=node.left
            else:
                node=stack.pop()
                res.append(node.val)
                node=node.right
        return res
        
    def postorderTraversal(self, root):
        stack=[]
        res=[]
        node=root
        while(stack or node):
            if node:
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                node=node.right
            else:
                node=stack.pop()
        return res[::-1]

BFS - 广度优先 - 层次遍历

层次遍历，用队列来帮助实现广度优先遍历
递归框架： 需要有一个level信息用于存储该节点所处的层次。问题：在哪里新增res的层次呢–解决方案，先判断l层次是否存在，不在的话新增。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root==None:
            return []
        res=[]
        def bfs(node,l):
            if node==None:
                return
            if l>len(res)-1:
                res.append([])
            res[l].append(node.val)
            bfs(node.left,l+1)
            bfs(node.right,l+1)
        bfs(root,0)
        return res
        

迭代框架：队列，先进先出，每层先统计队列的长度，确认要弹出的元素个数。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root==None:
            return []
        que=[root]
        res=[]
        l=0
        while(que):
            n=len(que)
            res.append([])
            for i in range(n):
                node=que.pop(0)
                res[l].append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            l+=1
        return res  

2. 深度、直径

二叉树的深度-最小、最大(自顶向下/自底向上)

111.二叉树的最小深度-BFS – 给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。
层次展开，第一个遇到的叶子结点。

112.二叉树的最大深度- BFS/DFS – 给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。遍历所有的路径，找出最大。

1. DFS - 自顶向下 - 在每个递归层级上，先访问节点来计算一些值，并在递归调用时将这些值传递给子节点。自顶向下的方案可以看作是一种先序遍历，根节点的深度是1，对于一个节点其深度为x, 那么我们将知道其子节点的深度。在递归调用时自顶向下将节点的深度作为一个参数传递下去。每一个节点都知道自己的深度，对于叶子节点，可以通过比较确定需不需要更新更大的深度。

2. DFS - 自底向上 -自底向上：在每个递归层级上，对所有的节点递归调用函数，然后根据返回值和根节点本身的值得到答案。自底向上的方案可以看作后序遍历。如果知道一个根节点，以其左子节点为根的最大深度为l，以其右子节点为根的最大深度为如，那么这个根节点所在子树的最大深度为$max(l,r)+1$（对于每个节点的答案，都可以在解决它的子节点问题的大难之后得到答案）

3. BFS - 最大level

class Solution {
    int _max_depth = 0;
public:
	// 111. 二叉树的最小深度-BFS
    int minDepth(TreeNode* root) {
        int res = 0;
        if (root == nullptr) {
            return res;
        }
        queue<TreeNode*> node_que;
        // std::queue<TreeNode*> node_que = {root}; 这么初始化要报错的，也不知道为啥？
        node_que.push(root);
        TreeNode* node = nullptr;
        while(!node_que.empty()) {
            res += 1;
            int n = node_que.size();
            for (int i = 0; i < n; i++) {
                node = node_que.front();
                node_que.pop();
                if (node->left == nullptr && node->right == nullptr) {
                    return res;
                }
                if (node->left != nullptr) {
                    node_que.push(node->left);
                }
                if (node->right != nullptr) {
                    node_que.push(node->right);
                }
            }
        }
        return res;
    }
	// 112.二叉树的最大深度-DFS
    int maxDepth(TreeNode* root) {
        // return bottom_up_dfs(root);
        // top_dowm_dfs(root, 0);
        _max_depth = BFS(root);
        return _max_depth;
    }

    int BFS(TreeNode* root) {
        int res = 0;
        if (root == nullptr) {
            return res;
        }
        queue<TreeNode*> node_que;
        node_que.push(root);
        TreeNode* node = nullptr;
        while (!node_que.empty()) {
            res++;
            int n = node_que.size();
            for (int i = 0; i < n; i++) {
                node = node_que.front();
                node_que.pop();
                if (node->left != nullptr) {
                    node_que.push(node->left);
                }
                if (node->right != nullptr) {
                    node_que.push(node->right);
                }
            }
        }
        return res;
    }

    int bottom_up_dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left = bottom_up_dfs(node->left);
        int right = bottom_up_dfs(node->right);
        return max(left, right) + 1;                  // 后序数位置，底向上，函数返回值+参数
    }

    void top_dowm_dfs(TreeNode* node, int level) {
        if (node == nullptr) {
            _max_depth = max(_max_depth, level);     // 类前序位置，顶向下， 只有参数
            return;
        }
        top_dowm_dfs(node->left, level+1);
        top_dowm_dfs(node->right, level+1);
    }
};

class Solution:
    def __init__(self):
        self.max_h = 0
    
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """
        @note 自顶向下
        """
        def preorder_dfs(root: TreeNode, h):
            if root== None:
                return 
            self.max_h = max(self.max_h, h)  # 先更新
            preorder_dfs(root.left, h+1)
            preorder_dfs(root.right, h+1)
        preorder_dfs(root, 1)
        return self.max_h
     
    def maxDepth2(self, root: Optional[TreeNode]) -> int:
        """
        @note 自底向上
        """
        def bottom_up_dfs(root: TreeNode):
            if root == None:
                return 0
            l_tree_h = bottom_up_dfs(root.left)
            r_tree_h = bottom_up_dfs(root.right)
            return max(l_tree_h, r_tree_h) + 1    # 后更新
        max_h = bottom_up_dfs(root)
        return max_h

二叉树的直径

543.二叉树的直径 – 给你一棵二叉树的根节点，返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。

class Solution {
    int _max_len = 0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        max_deep_dfs(root); 
        return _max_len - 1;  // 边数 
    }
    // 每个节点 左右子树最大深度 + 自身 构成一条路径，看看能否创造新的最长
    int max_deep_dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int max_left_deep = max_deep_dfs(node->left);   // 节点数
        int max_right_deep = max_deep_dfs(node->right); // 节点数
        _max_len = max(_max_len, max_left_deep + max_right_deep + 1);
        return max(max_left_deep, max_right_deep) + 1;
    }
};

路径总和 等于给定值 - I、II

112.路径总和 – 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。【深度优先】

1. 递归：直觉上至顶向下，是可行的思路。在每个节点处将目标值-节点值，将这个差值传给下一个节点，不断重复，如果叶子节点处刚好减为0，说明存在一条路径使得该路径上所有节点的值相加等于目标和。递归函数应该返回True 或者False 程序实现上可以遍历所有的路径，将所有的结果取或，但是只有一个为True 其实递归就可以终止，这个该怎么写。

2. 迭代：维护一个堆栈，用于储存每一个节点和其需要匹配的信息。每次从堆栈中弹出一个节点，判断该节点是否为叶子节点，如果为叶子节点，则判断对应的目标值-节点值是否为0；如果该节点不为叶子节点，将其子节点和相应的信息押入堆栈中。–堆栈如此维护：深度优先遍历的结构，遍历完一条路径之后再去遍历其他的路径。第一条走过的是最右边的路径，是一个由右往左扫描的过程。

113.路径总和 II - 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。

class Solution {
    vector<vector<int>> _res;
public:
	// 112.路径总和
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 记录根节点->当前节点路径和，如果当前节点是叶子结点，就返回
        bool res_has = dfs_hasPathSum(root, targetSum);
        return res_has;
    }
    bool dfs_hasPathSum(TreeNode* node, int targetSum) {
        if (node == nullptr) {
            return false;
        }
        if (node->left == nullptr && node->right == nullptr) {
            return targetSum == node->val;
        }
        bool left_has = dfs_hasPathSum(node->left, targetSum - node->val);
        bool right_has = dfs_hasPathSum(node->right, targetSum - node->val);
        return left_has || right_has;
    }
   
	// 113. 路径总和 II - DFS path.emplace_back(node->val); path.pop_back();
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs_path_sum(root, targetSum, path);
        return _res;
    }
    void dfs_path_sum(TreeNode* node, int targetSum, vector<int>& path) {
        if (node == nullptr){
            return;   
        }
        path.emplace_back(node->val);
        if (node->left == nullptr && node->right == nullptr && targetSum == node->val) {
            _res.push_back(path);
            path.pop_back();    // return 前pop
            return;
        }
        dfs_path_sum(node->left, targetSum - node->val, path);
        dfs_path_sum(node->right, targetSum - node->val,path);
        path.pop_back();       // return 前pop
    }
};

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root==None:
            return False
        stack=[(root,sum)]
        while(stack):
            node,target=stack.pop()
            if node.left==None and node.right==None and node.val-target==0:
                return True
            if node.left:
                stack.append((node.left,target-node.val))
            if node.right:
                stack.append((node.right,target-node.val))
        return False

路径和 最大

124.二叉树中的最大路径和 – 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

/**
 * 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 {
    int _res = -1001;
public:
    int maxPathSum(TreeNode* root) {
        int root_devoted = node_devoted_dfs(root);
        return _res;
    }

    int node_devoted_dfs(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left_devoted = max(node_devoted_dfs(node->left), 0);
        int right_devoted = max(node_devoted_dfs(node->right), 0);
        int candidate_path = left_devoted + right_devoted + node->val;
        _res = max(candidate_path, _res);
        // 左右子树仅选一遍，继续向上 退出递归，更新最优解
        int node_devoted = max(left_devoted, right_devoted) + node->val;
        return node_devoted;
    }
};

3. 二叉树构建

根据中序和后序遍历序列构造二叉树

inorder=[9,3,15,20,7] 左根右
postorder=[9,15,7,20,3] 左右根，逆序就是根右左：[3,20,7,15,9]
由后序遍历中可知根节点是3，在中序遍历中可以确定左右子树序列是多少。如何提取下一个根节点呢？取根和左右子树递归构造该如何衔接。
inorder 用来控制递归出口
postorder 才是提供根节点的源泉。

class Solution(object):
    def __init__(self):
        self.root_idx = 0
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        postorder_inver = postorder[::-1]
        def helper(left_idx=0, right_idx=len(postorder)):
            if left_idx == right_idx:
                return None
            root_val = postorder_inver[self.root_idx]
            self.root_idx += 1
            root = TreeNode(root_val)
            # 只有一个节点时[a]， inorder_idx = 0, left_idx=0, inorder_idx+1=1,
            # 左右节点调用都返回None
            inorder_idx = inorder.index(root_val)
            root.right = helper(inorder_idx+1, right_idx)
            root.left = helper(left_idx, inorder_idx)
            return root
        return helper()

根据前序和中序遍历序列构造二叉树

preorder=[3,9,20,15,7] 中左右
inorder=[9,3,15,20,7] 左中右
一个根节点可以将中序遍历划分为左一半，右一半。
全局变量pre_idx，每次运行一次helper函数一次加1，取下一根节点；直至左子树运行完，对应的根节点下标也应该遍历完全了。
剩余问题：index不因该是根节点的在中序遍历中的下标么？左子树包含的内容不是应该为[0,index-1] 根递归出口有关，不是直接索引元素。

class Solution(object):
    def __init__(self):
        self._root_idx = 0
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # 前序-中左右， 中序-左右中
        def helper(left_idx=0, right_idx=len(inorder)):
            if left_idx == right_idx:
                return None
            root_val = preorder[self._root_idx]
            self._root_idx += 1
            root = TreeNode(root_val)
            inorder_idx = inorder.index(root_val)
            root.left = helper(left_idx, inorder_idx)
            root.right = helper(inorder_idx+1, right_idx)
            return root
        return helper()

class Solution {
    int _root_idx = 0;
public:
	// 105. 从前序与中序遍历序列构造二叉树
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build_from_pre_inorder(preorder, inorder, 0, inorder.size()-1);
    }
    TreeNode* build_from_pre_inorder(vector<int>& preorder, vector<int>& inorder, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        // 左中右 + 中左右 =》 
        int val = preorder.at(_root_idx);
        _root_idx++;
        TreeNode* node = new TreeNode(val);
        int val_idx_at_inoder = left;
        while(val_idx_at_inoder <= right) {
            if (inorder.at(val_idx_at_inoder) == val) {
                break;
            }
            val_idx_at_inoder++;
        }
        node->left = build(preorder, inorder, left, val_idx_at_inoder-1);
        node->right = build(preorder, inorder, val_idx_at_inoder+1, right);
        return node;
    }
    // 106. 从中序与后序遍历序列构造二叉树
     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        _root_idx = postorder.size() - 1;
        return build_from_inorder_post(inorder, postorder, 0, postorder.size()-1);
        
    }
    TreeNode* build_from_inorder_post(vector<int>& inorder, vector<int>& postorder, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        // 左中右 + 左右中 =》 
        int val = postorder.at(_root_idx);
        _root_idx--;
        TreeNode* node = new TreeNode(val);
        int val_idx_at_inoder = left;
        while(val_idx_at_inoder <= right) {
            if (inorder.at(val_idx_at_inoder) == val) {
                break;
            }
            val_idx_at_inoder++;
        }
        node->right = build(inorder, postorder, val_idx_at_inoder+1, right);
        node->left = build(inorder,  postorder, left, val_idx_at_inoder-1);
        return node;
    }
};

二叉树的序列化和反序列化

将二叉树序列化为一个字符串，将得到的字符串反序列化为二叉树。
说明：不要使用类成员/全局/静态变量来存储状态，序列化和反序列化算法应该是无状态的。–什么是无状态？

序列化和反序列化递归顺序一致就可以。

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def dfs_serialize(node, iter_str):
            if node == None:
                iter_str += "None,"
                return iter_str
            iter_str += "{0},".format(node.val)
            iter_str = dfs_serialize(node.left, iter_str)
            iter_str = dfs_serialize(node.right, iter_str)
            return iter_str
        return dfs_serialize(root, "")

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def dfs_deserialize(data_list):
            # print(data_list)
            if data_list[0] == "None":
                data_list.pop(0)
                return None
            node = TreeNode(int(data_list[0]))
            data_list.pop(0)
            node.left = dfs_deserialize(data_list)
            node.right = dfs_deserialize(data_list)
            return node
        data_list = data.split(",")
        return dfs_deserialize(data_list)

4. Other

226. 翻转二叉树

226.翻转二叉树 – 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

class Solution(object):
	# 递归-自低向上的交换过程
    def invertTree_bottom_up(self, root):
        if root==None:
            return
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left,root.right=root.right,root.left
        return root
        
    # 迭代-自顶向下的交换过程
    def invertTree_top_down(self, root):
        if root:
            q=[root]
        else:
            return root
        while(q):
            curr=q.pop(0)
            curr.left,curr.right=curr.right,curr.left
            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
        return root

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        dfs_bottom_up(root);
        return root;
    }
    void dfs_bottom_up(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        // 先序位置 和 后序位置 都一样
        dfs_bottom_up(node->left);
        dfs_bottom_up(node->right);
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
    }
};

114. 二叉树展开为链表

114.二叉树展开为链表 --给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

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

        TreeNode* right = node->right;  
        node->right = node->left;
        node->left = nullptr;
        // key
        TreeNode* tmp_p = node;
        while(tmp_p->right != nullptr) {
            tmp_p = tmp_p->right;
        }
        tmp_p->right = right;
    }
};

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

116.填充每个节点的下一个右侧节点指针 – 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：填充它的每个next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

117.填充每个节点的下一个右侧节点指针 II – 一般二叉树，递归出口改成或

class Solution {
public:
    Node* connect(Node* root) {
        if (root == NULL) {
            return root;
        }
        dfs(root->left, root->right);
        return root;
    }
    void dfs(Node* left, Node* right) {
        if (left == NULL && right == NULL) {
            return;
        }
        left->next = right;   // 先序位置
        dfs(left->left, left->right);  // 左子树
        dfs(right->left, right->right); // 右子树
        dfs(left->right, right->left); // 左右子树链接
    }
};

    Node* connect_117(Node* root) {
        if (root == NULL) {
            return root;
        }
        dfs(root->left, root->right);
        return root;
    }

    void dfs_117(Node* node1, Node* node2) {
        if (node1 == NULL || node2 == NULL) {  // 改成或
            return;
        }
        node1->next = node2;
        dfs(node1->left, node1->right);
        dfs(node1->right, node2->left);
        dfs(node2->left, node2->right);
    }

101. 对称二叉树

101.对称二叉树 – 给你一个二叉树的根节点 root ， 检查它是否轴对称。解题关键：每次取到需要相互比较的两个节点。

递归：所以两个指针分别从根节点开始，一个往左子树游走，一个往右子树游走，依次查看镜面对称的节点是相等。验证root 子树和root子树是不是镜面对称的。如果是的话，单独的一棵root树是镜面对称的。
迭代：队列初始化为[root,root]，将需要比较的点放在相邻位置。每次弹出两个节点，如果两个节点相同时，node1.left 和node2.right 放入队列；将node1.right与node2.left放入队列。这样押入弹出直至对比完该对比的节点。

class Solution(object):
	# 递归
    def isSymmetric(self, root):
        def ismirror(node1,node2):
            if node1==None and node2==None:
                return True
            if node1==None or node2==None:
                return False
            return node1.val==node2.val and ismirror(node1.left,node2.right) and ismirror(node1.right,node2.left)
        flag=ismirror(root,root) # root 和root为镜像，root自己本身为镜像
        return flag
    # 迭代
    def isSymmetric(self, root):
        que=[root, root]
        while(que):
            node1=que.pop(0)
            node2=que.pop(0)
            if node1==None and node2==None:
                continue
            if node1==None or node2==None:
                return False
            if node1.val!=node2.val:
                return False
            que.append(node1.left)
            que.append(node2.right)
            que.append(node1.right)
            que.append(node2.left)
        return True

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isSymmetric_dfs(root, root);
    }

    bool isSymmetric_dfs(TreeNode* left_node, TreeNode* right_node) {
        if (left_node == nullptr && right_node == nullptr) {
            return true;
        }
        if (left_node == nullptr || right_node == nullptr) {
            return false;
        }
        if (left_node->val != right_node->val) {
            return false;
        }
        
       bool is_left_symmetric = isSymmetric_dfs(left_node->left, right_node->right);
       bool is_right_symetric = isSymmetric_dfs(left_node->right, right_node->left);
       return is_left_symmetric && is_right_symetric;
    }

};

合并两棵二叉树

leetcode617: 两棵树有公共结点处的值为两数对应节点值想加

递归

class Solution(object):
    def mergeTrees(self, t1, t2):
        if not t1 and not t2:
            return None
        root=TreeNode(0)
        if t1 and t2:
            root.val=t1.val+t2.val
            root.left=self.mergeTrees(t1.left,t2.left)
            root.right=self.mergeTrees(t1.right,t2.right)
        elif t1:
            root.val=t1.val
            root.left=self.mergeTrees(t1.left,None)
            root.right=self.mergeTrees(t1.right,None)
        else:
            root.val=t2.val
            root.left=self.mergeTrees(None,t2.left)
            root.right=self.mergeTrees(None,t2.right)
        return root
        class Solution(object):
    def mergeTrees2(self, t1, t2):
        if t1==None:
            return t2
        if t2==None:
            return t1
        t1.val+=t2.val
        t1.left=self.mergeTrees2(t1.left,t2.left)
        t1.right=self.mergeTrees2(t1.right,t2.right)
        return t1

迭代-首先把两棵树的根节点入栈，栈中的每个元素都会存放两个根节点，并且栈顶的元素表示当前需要处理的节点。
以t1作为最后的输出返回，
当前结点的处理（ 在stack里面的东西都是非空的）：
两者相加的值放入t1.val
子结点的处理：
t1没有做孩子，t2的左孩子给t1.
t1,t2同时有左孩子，将其同时入栈，
右孩子的处理同理。

class Solution(object):
    def mergeTrees(self, t1, t2):
        if t1==None:
            return t2
        if t2==None:
            return t1
        stack=[(t1,t2)]
        while(stack):
            node1,node2=stack.pop() # 在stack里面的东西都是非零的
            node1.val+=node2.val
            if node1.left==None:
                node1.left=node2.left
            elif node1.left and node2.left:  # 1.left 和2.left同时非零
                stack.append([node1.left,node2.left])
            if node1.right==None:
                node1.right=node2.right      # 放过来之后就有。
            elif  node1.right and node2.right:  # 1.left 和2.left同时非零
                stack.append([node1.right,node2.right])
        return t1

二叉树的最近公共祖先

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
官方思路1:递归
递归遍历整棵树，定义$f_x$表示x节点的子树中是否包含p节点或者q节点，如果包含则为true.采用自底向上从叶子节点开始更新，保证满足条件的公共祖先深度最深。

class Solution(object):
    def __init__(self):
        self.ans = None
    def lowestCommonAncestor(self, root, p, q):
        def bottom_up(node):
            if node == None:
                return False
            left_mark = bottom_up(node.left)  # 左右子树中是否包含pq节点
            right_mark = bottom_up(node.right)
            current_mark = (node.val == p.val) or (node.val == q.val)
            # print(node.val, left_mark, right_mark, current_mark)
            if (current_mark + left_mark + right_mark == 2):
                self.ans = node
                return True
            return current_mark or right_mark or left_mark
        bottom_up(root)
        return self.ans

官方思路2:储存父节点
用hash表存储所有节点的父亲节点，然后利用节点的父亲节点的信息从p往上跳，直至根节点，记录已经访问过的节点；再从q节点开始不断往上跳，每次上跳一个节点就去p已访问的节点中寻找是否已经访问过该节点。第一次遇到的p已经访问的节点，则该节点为答案。
难点1：父亲节点hash表。{child1:root1,child2:root1},只要遍历过二叉树的所有节点，就可以实现这个。
难点2:从p开始，不断在父亲hash表中找父亲节点，直至找不到父亲节点的跟节点，将所有路径放入[]中。
技巧：还是将节点放进去。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.father_hash = {}
        self.vist_hash = {}
    def lowestCommonAncestor(self, root, p, q):
        def dfs_contruct_father_hash(node):
            if node == None:
                return 
            if node.left:
                self.father_hash[node.left] = node
            if node.right:
                self.father_hash[node.right] = node
            dfs_contruct_father_hash(node.left)
            dfs_contruct_father_hash(node.right)
        self.father_hash[root] = None
        dfs_contruct_father_hash(root)
        node = p
        while(p):
            self.vist_hash[p] = True
            p = self.father_hash[p]
        node = q
        while(q):
            if self.vist_hash.get(q):
                return q
            q = self.father_hash[q]
        return None

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

1. 填充一个完美二叉树的每个节点的下一个右侧节点。完美二叉树说的是，所有叶子节点都在同一层。
   思路：关键找到每一个节点的下一个节点，那不就是二叉树的层次遍历。
   每层的节点的next指针指其下一个节点，用l来控制该层的最后一个节点指向None。

2. 填充每个节点的下一个右侧节点指针2
   给定一个二叉树，填充它每个next指针指向右侧节点，同一层的最右侧节点填充为None.
   思路：不是一棵完美的二叉树，不过还是树的层次遍历，上一题的框架依旧可以使用。
   代码只diff 了一行

# python 
class Solution(object):
    def connect(self, root):
        """
        填充一个完美二叉树的每个节点的下一个右侧节点
        """
        if root == None:
            return root
        node_que = [root]
        while(node_que):
            level_node_num = len(node_que)
            i = 0
            while(node_que and i < level_node_num):
                node = node_que.pop(0)
                if i < level_node_num - 1:
                    node.next = node_que[0]
                if node.left:      # 左右节点同时存在，所以只需要判断一个非空即可
                    node_que.append(node.left)
                    node_que.append(node.right)
                i+=1
        return root
    def connect(self, root):
        """
        填充每个节点的下一个右侧节点指针2
        """
        if root == None:
            return root
        node_que = [root]
        while(node_que):
            level_node_num = len(node_que)
            i = 0
            while(node_que and i < level_node_num):
                node = node_que.pop(0)
                if i < level_node_num - 1:
                    node.next = node_que[0]
                if node.left:
                    node_que.append(node.left)
                if node.right:      // 与connect1 diff 的行
                    node_que.append(node.right)
                i+=1
        return root

完全二叉树 解法还如下。非完全二叉树，用以下框架没改出来，似乎需要写一大堆判断条件。

class Solution {
public:
    Node* connect(Node* root) {
        if (root == NULL) {
            return root;
        }
        dfs(root->left, root->right);
        return root;
    }

    void dfs(Node* node1, Node* node2) {
        if (node1 == NULL || node2 == NULL) {
            return;
        }
        node1->next = node2;
        dfs(node1->left, node1->right);
        dfs(node1->right, node2->left);
        dfs(node2->left, node2->right);
    }
};

剑指 Offer 26. 树的子结构

判断：小树B是否是大树A的一部分，需要以大树A的每个为根节点进行匹配判断。
算法：判断两个节点是否相等，相同，递归处理，不相同跳出递归隐士遍历A的所有节点。

class Solution(object):
    def isSubStructure(self, A, B):
        """
        :type A: TreeNode
        :type B: TreeNode
        :rtype: bool
        """
        def dfs(node1, node2):
            if node2 == None:        # B树到达叶子节点了
                return True
            if node1 == None or node1.val != node2.val:  # A树叶子，B树非叶子 or 两者的值不相等
                return False
            return dfs(node1.left,node2.left) and dfs(node1.right,node2.right)
        return bool(A and B) and (dfs(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right,B))

剑指 Offer 27. 二叉树的镜像

将二叉树以根节点为中心，进行中心对称处理
算法：针对每个节点交换每个节点的左右子树，递归处理左右子树

class Solution(object):
    def mirrorTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """ 
        def dfs(node):
            if node == None :
                return
            node.left, node.right = node.right, node.left  # 交换左右子树
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return root