二叉树总结
- 二叉搜索树
  - 将有序数组转换为二叉搜索树 (easy 中序)
  - 二叉搜索树的最近公共祖先 (easy)
  - 二叉树的最近公共祖先 (medium 后序)
  - 验证二叉搜索树 (medium 中序)
  - 二叉搜索树中第K小的元素(medium 中序)
- 层序遍历
  - 二叉树的层次遍历 (medium)
  - 二叉树的锯齿层次遍历 (medium 标志位)
  - 二叉树的右视图 (medium)
  - 填充同一层的兄弟节点 (medium 链表)
- 前序遍历
  - 合并二叉树 (easy)
  - 二叉树的所有路径 (easy 路径)
  - 二叉树的前序遍历(medium)
  - 求根到叶子节点数字之和 (medium 路径)
  - 路径总和II (medium 路径)
  - 从前序与中序遍历序列构造二叉树 (medium 分治)
- 中序遍历
  - 二叉树的中序遍历 (medium)
- 后序遍历
  - 二叉树的最大深度 (easy)
  - 平衡二叉树 (easy)
  - 具有所有最深结点的最小子树 (medium)
  - 二叉树中的最大路径和 (hard 动态规划)
  - 二叉树的后序遍历(easy)
- 其他
  - 对称二叉树 (easy)
  - 二叉树的序列化与反序列化 (hard)

二叉树总结

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]

返回它的最大深度 3 。

解答

二叉树的后序遍历(递归)，在递归的每一层，得到左子树和右子树的深度，取它们较大值，就得到当前递归层所能达到的最大深度；而整个二叉树的最大深度就是根节点所在递归层得到的深度。

/**
 * 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 maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        
        int num = 1;
        int num_l = maxDepth(root->left);
        int num_r = maxDepth(root->right);
        num += num_l > num_r ? num_l : num_r;
        return num;
    }
};

合并二叉树

LeetCode中文

LeetCode英文

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

注意: 合并必须从两个树的根节点开始。

解答

二叉树的后序遍历(递归)，同时遍历两棵二叉树，对比两棵所遍历到的节点，分为以下几种情况：

tree1节点为空，tree2节点非空，返回tree2节点；
tree1节点非空，tree2节点为空，返回tree1节点；
tree1节点和tree2节点都非空，新建一个节点，它的值为两节点之和；
tree1节点和tree2节点都为空，返回空节点nullptr。

经过整个遍历过程，就可以构造出合并后的二叉树。

C++代码

/**
 * 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) {
        if(!t1) return t2;
        if(!t2) return t1;
        
        TreeNode* node = new TreeNode(t1->val + t2->val);
        node->left = mergeTrees(t1->left,t2->left);
        node->right = mergeTrees(t1->right,t2->right);
        return node;
        
    }
};

Python代码

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        
        node = TreeNode(t1.val + t2.val)
        node.left = self.mergeTrees(t1.left,t2.left)
        node.right = self.mergeTrees(t1.right,t2.right)
        
        return node

将有序数组转换为二叉搜索树

LeetCode中文

LeetCode英文

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解答

考察二叉树的中序建立和平衡二叉树性质，利用平衡二叉搜索树(平衡BST)的性质，平衡BST的中序遍历节点值组成的数组，它的根节点一定是在数组的中间位置。因此对每个子树同样适用这个规律，这就是递归的思想。

对每一个子树组成的数组，有以下几种情况：

数组为空：已经到了空节点，直接返回nullptr；
数组非空：新建一个节点作为当前子树的根节点，它的值取为数组中间位置的值，然后将数组左边部分构成的子数组用来构造左子树，将数组右边部分构成的子数组用来构造右子树。

C++代码

/**
 * 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* getTree(vector<int>& vec,int l,int r)
    {
        if(l <= r)
        {
            int mid = l + (r - l) / 2;
            TreeNode* node = new TreeNode(vec[mid]);
            node->left = getTree(vec,l,mid - 1);
            node->right = getTree(vec,mid + 1,r);
            return node;
        }
        else
            return nullptr;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0)
            return nullptr;
        
        return getTree(nums,0,nums.size() - 1);
    }
};

Python代码

# Definition for a binary tree node.
# class TreeNode:

#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def recursion(self,nums: List[int],l: int,r: int) -> TreeNode:
        if l > r:
            return None
        m = (l + r) // 2
        node = TreeNode(nums[m])
        node.left = self.recursion(nums,l,m - 1)
        node.right = self.recursion(nums,m + 1,r)
        return node
    
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        n = len(nums)
        return self.recursion(nums,0,n - 1)

二叉树的所有路径

LeetCode中文

LeetCode英文

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

解答

考察树的前序遍历，前序遍历二叉树可以走过每条路径，在每条路径途中每遇到一个节点就加到路径字符串res中，当到达叶子节点的时候说明走完一条路径，此时需要退回，而退回的时候从res中弹出当前节点。

注意：->符号的处理。

C++代码

/**
 * 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:
    void recursion(TreeNode* root,string& str)
    {
        string s = to_string(root->val);
        str += s + "->";
        int num = s.size();
        
        if(!root->left && !root->right)
        {
            for(int i=0;i<2;i++)
                str.pop_back();
            res.push_back(str);
            for(int i=0;i<num;i++)
                str.pop_back();
            return;
        }
            
        if(root->left)
            recursion(root->left,str);
        
        if(root->right)
            recursion(root->right,str);
        
        for(int i=0;i<num+2;i++)
            str.pop_back();
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        if(!root)
            return res;
        
        int n = 0;
        recursion(root,str);
        return res;
    }
    
    private:
    vector<string> res;
    string str;
};

Python代码

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

class Solution:
    def recursion(self,root: TreeNode):
        if root is None:
            return
        
        self.str = self.str + str(root.val)
        
        if not root.left and not root.right:
            self.res.append(self.str)
            self.str = self.str.rstrip(str(root.val))
            return
        
        self.str = self.str + "->"
        
        if root.left:
            self.recursion(root.left)
        if root.right:
            self.recursion(root.right)
        
        self.str = self.str.rstrip("->")
        self.str = self.str.rstrip(str(root.val))
        
        
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        self.res = []
        self.str = ""
        
        self.recursion(root)
        
        return self.res

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

LeetCode中文

LeetCode英文

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

解答

方法1

利用二叉搜索树的性质，从树的根节点往下找最近祖先，设p,q中较大值为pv，较小值为qv。分为以下几种情况

如果当前节点的值 > pv，公共祖先在当前子树的右子树，到右子树中去找；
如果当前节点的值 < qv，公共祖先在当前子树的左子树，到左子树中去找；
当前节点的值 > qv 且 < pv，公共祖先就是当前节点；
其他情况，公共祖先就在p,q两个之间，找到和其中一个结点值相等的结点即可。

C++代码

/**
 * 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* recursion(TreeNode* root,TreeNode* p,TreeNode* q)
    {
        if(!root)
            return nullptr;
        
        int v1 = p->val;
        int v2 = q->val;
        if(root->val > v1 && root->val < v2)
            return root;
        if(root->val > v2)
            return recursion(root->left,p,q);
        if(root->val < v1)
            return recursion(root->right,p,q);
        
        return root->val == v1 ? p : q;
        
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
            return nullptr;
        
        if(p->val > q->val)
            swap(p,q);
        
        TreeNode* res = recursion(root,p,q);
        
        return res;
    }
};

Python代码

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

class Solution:
    def findNode(self,node: TreeNode,a: int,b: int):
        if not node:
            return None
        tmp = node.val
        if tmp >= a and tmp <= b:
            return node
        elif tmp < a:
            return self.findNode(node.right,a,b)
        elif tmp > b:
            return self.findNode(node.left,a,b)
        
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        pa = min(p.val,q.val)
        pb = max(p.val,q.val)
        return self.findNode(root,pa,pb)

其他两种方法参见二叉树的最近公共祖先 。

平衡二叉树

LeetCode中文

LeetCode英文

给定一个二叉树，判断它是否是高度平衡的二叉树。

高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1：

给定二叉树 [3,9,20,null,null,15,7]

返回true

示例 2：

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回false

解答

根据平衡二叉树的定义

平衡二叉树（AVL树）：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

因此，需要验证树的每个子树都是平衡二叉树，这很适合递归地去处理。

对于每一层递归对应的子树，有以下几种情况：

它的左右子树不全是AVL树，则整棵树就不是AVL树；
它的左右子树都是平衡二叉树，那么就比较左右子树的深度差值，如果差值小于等于1，则当前子树是AVL树，否则不是AVL树。

/**
 * 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 recursion(TreeNode* root,int& depth)
    {
        if(!root)
        {
            depth = 0;
            return true;
        }
        
        int depth_l = 0;
        int depth_r = 0;
        bool l_flag = recursion(root->left,depth_l);
        bool r_flag = recursion(root->right,depth_r);
        
        if(!l_flag || !r_flag || abs(depth_l - depth_r) > 1)
            return false;
        
        depth = max(depth_l,depth_r) + 1;
        return true;
    }
    bool isBalanced(TreeNode* root) {
        if(!root)
            return true;
        
        int depth = 0;
        return recursion(root,depth);
    }
};

对称二叉树

LeetCode中文

LeetCode英文

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

解答

同时对二叉树进行root->left->right和root->right->left的遍历，判断遍历到的每个值是否相等。

注意：考察二叉树前序遍历的递归方法和非递归方法。

递归

/**
 * 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 recursion(TreeNode* p1,TreeNode* p2)
    {
        if(!p1 && !p2) return true;
        if(p1 && p2 && p1->val == p2->val)
        {
            return recursion(p1->left,p2->right) && recursion(p1->right,p2->left);
        }
        
        return false;
    }
    
    bool isSymmetric(TreeNode* root) {
        return recursion(root,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 Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        
        stack<TreeNode*> sta1;
        stack<TreeNode*> sta2;
        sta1.push(root);
        sta2.push(root);
        while(!sta1.empty() && !sta2.empty())
        {
            TreeNode* cur1 = sta1.top();
            sta1.pop();
            TreeNode* cur2 = sta2.top();
            sta2.pop();
            
            if(!cur1 && cur2)
                return false;
            if(cur1 && !cur2)
                return false;
            if(cur1 && cur2)
            {
                if(cur1->val == cur2->val)
                {
                    sta1.push(cur1->right);
                    sta1.push(cur1->left);
                
                    sta2.push(cur2->left);
                    sta2.push(cur2->right);
                }
                else
                    return false;
            }
        }
        
        if(sta1.empty() && sta2.empty())
            return true;
        else 
            return false;
    }
};

二叉树的最近公共祖先

LeetCode中文

LeetCode英文

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解答

方法1

分为以下几个步骤：

找到从根到p指向结点的路径，并存储在一个向量或数组中；
找到从根到q指向结点的路径，并存储在一个向量或数组中；
同时从这两条路径起点开始走，直到遇到一个不同的节点，则它前面的那个即为p,q的最近公共祖先。

C++代码

/**
 * 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 findNode(TreeNode* root,TreeNode* target,vector<TreeNode*>& vec)
    {
        if(!root)
            return false;
        
        vec.push_back(root);
        
        if(root == target)
        {
            return true;
        }
        
        if(findNode(root->left,target,vec))
            return true;
        if(findNode(root->right,target,vec))
            return true;
        
        vec.pop_back();
        return false;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        findNode(root,p,path_p);
        findNode(root,q,path_q);
        
        int i = 0;
        for(;i < path_p.size() && i < path_q.size();i++)
        {
            if(path_p[i] != path_q[i])
                break;
        }
        
        return path_p[i-1];
    }
    
private:
    vector<TreeNode*> path_p,path_q;
};

Pythono代码

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

class Solution:
    def findPath(self,root: TreeNode,path: List,node: TreeNode) -> bool:
        if not root:
            return False
        if root == node:
            path.append(root)
            return True
        
        path.append(root)
        l = self.findPath(root.left,path,node)
        r = self.findPath(root.right,path,node)
        if l or r:
            return True
        
        path.pop()
        return False
        
        
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        path_p = []
        path_q = []
        
        self.findPath(root,path_p,p)
        self.findPath(root,path_q,q)
        
        i = 0
        while i < len(path_p) and i < len(path_q):
            if path_p[i] != path_q[i]:
                break
            i += 1
            
        if i == len(path_p):
            return path_p[-1]
        if i == len(path_q):
            return path_q[-1]

        return path_p[i - 1]

方法2

从根节点开始遍历二叉树，对二叉树的每一个子树（包括整个树），设它的根节点为root如果node1和node2中的任一个和root匹配，那么root就是最低公共祖先。如果都不匹配，则分别递归左、右子树，如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先. 如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

具体过程：后序遍历二叉树，对每个子树，有以下几种情况：

当前节点为空，返回nullptr；
当前节点在p,q两节点之间，返回相等的那个；
以上条件都不符合，得到左右子树后序遍历的结果lp和rp：
- 如果lp和rp都是非空，则返回当前节点（当前节点就是最近祖先）；
- lp和rp有一个为空，返回lp,rp中非空的那个。

最后，当遍历完整个二叉树，得到的就是p,q节点的最近公共祖先。

C++代码

/**
 * 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* recursion(TreeNode* root,TreeNode* p,TreeNode* q)
    {
        if(!root) return nullptr;
        if(root == p) return p;
        if(root == q) return q;
         
        TreeNode* lp = recursion(root->left,p,q);
        TreeNode* rp = recursion(root->right,p,q);
        
        if(!lp) return rp;
        if(!rp) return lp;
        return root;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return recursion(root,p,q);
    }
};

Python代码

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

class Solution:
    def recursion(self,root: TreeNode,p: TreeNode,q: TreeNode) -> TreeNode:
        if not root:
            return None
        if root == p:
            return p
        if root == q:
            return q
        l = self.recursion(root.left,p,q)
        r = self.recursion(root.right,p,q)
        
        if not l and not r:
            return None
        if not l:
            return r
        if not r:
            return l
        return root
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.recursion(root,p,q)

从前序与中序遍历序列构造二叉树

LeetCode中文

LeetCode英文

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

解答

利用二叉树前序和中序遍历的性质，前序序列的第一个元素是树的根结点，而对于中序序列，在根节点左半部分是树的左子树，在根节点右半部分是树的右子树。对于二叉树的每个子树都有这样的规律，这很符合递归的特点。因此，在递归函数中，利用这一规律处理每个子树。

C++代码

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty())
            return nullptr;
        
        int root = preorder.front();
        auto it = find(inorder.begin(),inorder.end(),root);
        int a = it - inorder.begin();
        TreeNode* head = new TreeNode(root);
        
        vector<int> pre_l(preorder.begin() + 1,preorder.begin() + 1 + a);
        vector<int> in_l(inorder.begin(),it);
        vector<int> pre_r(preorder.begin() + 1 + a,preorder.end());
        vector<int> in_r(it + 1,inorder.end());
        
        head->left = buildTree(pre_l,in_l);
        head->right = buildTree(pre_r,in_r);
        
        return head;
    }
};

优化：改变递归函数形参为数组下标范围，减少数组拷贝消耗的时间。

/**
 * 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* recursion(vector<int>& preorder,int pre_l,int pre_r,vector<int>& inorder,int in_l,int in_r)
    {
        if(pre_l > pre_r) return nullptr;
        if(pre_l == pre_r) return new TreeNode(preorder[pre_l]);
        
        int rt_val = preorder[pre_l];
        auto it = find(inorder.begin()+in_l,inorder.begin()+in_r+1,rt_val);
        
        int left = it - (inorder.begin() + in_l);
        
        TreeNode* root = new TreeNode(rt_val);
        root->left = recursion(preorder,pre_l + 1,pre_l + left,inorder,in_l,in_l + left - 1);
        root->right = recursion(preorder,pre_l + left + 1,pre_r,inorder,in_l + left + 1,in_r);
        
        return root;
    }
    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return recursion(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};

Python代码

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

class Solution:
    def recursion(self,preorder,pre_l,pre_r,inorder,in_l,in_r):
        if pre_l > pre_r:
            return None
        if pre_l == pre_r:
            return TreeNode(preorder[pre_l])
        
        root = preorder[pre_l]
        node = TreeNode(root)
        idx = inorder.index(root)
        
        node.left = self.recursion(preorder,pre_l + 1,pre_l + idx - in_l,inorder,in_l,idx - 1)
        node.right = self.recursion(preorder,pre_l + idx - in_l + 1,pre_r,inorder,idx + 1,in_r)
        
        return node
        
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        return self.recursion(preorder,0,len(preorder) - 1,inorder,0,len(inorder) - 1)

求根到叶子节点数字之和

LeetCode中文

LeetCode英文

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

示例 2:

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

解答

树的前序遍历 + 字符串数字转换（详细思路参见：二叉树的所有路径）。

C++代码

/**
 * 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 sumNumbers(TreeNode* root) {
        int sum = 0,tmp = 0;
        
        recursion(root,sum,tmp);
        
        return sum;
    }
    
    void recursion(TreeNode* root,int& sum,int& tmp)
    {
        if(!root) return;
        
        tmp = tmp * 10 + root->val;
        
        if(!root->left && !root->right)
        {
            sum += tmp;
            tmp = (tmp - root->val) / 10;
            return;
        }
        
        if(root->left)
        {
            recursion(root->left,sum,tmp);
        }
        if(root->right)
        {
            recursion(root->right,sum,tmp);
        }
        
        tmp = (tmp - root->val) / 10;
    }
};

Python代码

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

class Solution:
    def recursion(self,root: TreeNode):
        if not root:
            return
        self.tmp = self.tmp * 10 + root.val
        
        if not root.left and not root.right:
            self.res = self.res + self.tmp
            self.tmp = int((self.tmp - root.val) / 10)
            return
        
        if root.left:
            self.recursion(root.left)
        if root.right:
            self.recursion(root.right)
            
        self.tmp = int((self.tmp - root.val) / 10)
        
    def sumNumbers(self, root: TreeNode) -> int:
        self.res = 0
        self.tmp = 0
        self.recursion(root)
        
        return self.res

二叉树的层次遍历

LeetCode中文

LeetCode英文

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:

给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解答

考察二叉树的层序遍历，利用队列结构queue实现。层序遍历的过程中需要将每层的元素分开存放，定义两个指针pre和next，pre指向当前层的最后一个节点，next指向下一层的最后一个节点，当遍历到的当前结点cur == pre时，令pre = next，next一直更新，它指向已入队列的最后一个节点。

C++代码

/**
 * 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) {
        vector<vector<int >> res;
        if(!root)
            return res;
        
        vector<int> vec;
        queue<TreeNode*> que;
        
        TreeNode* pre = root;
        TreeNode* next = nullptr;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* cur = que.front();
            que.pop();
            vec.push_back(cur->val);
            
            if(cur->left)
            {
                que.push(cur->left);
                next = cur->left;
            }
                
            if(cur->right)
            {
                que.push(cur->right);
                next = cur->right;
            }
            
            if(cur == pre)
            {
                res.push_back(vec);
                vec.clear();
                pre = next;
            }
        }
        return res;
    }
};

Python代码

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        res = []
        que = []
        vec = []
        pre = root
        nex = None
        que.append(root)
        while len(que) > 0:
            cur = que.pop(0)
            vec.append(cur.val)
            
            if cur.left:
                que.append(cur.left)
                nex = cur.left
            if cur.right:
                que.append(cur.right)
                nex = cur.right
            if cur == pre:
                pre = nex
                res.append(vec)
                vec = []
                
        return res

二叉树的右视图

LeetCode中文

LeetCode英文

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解答

树的层序遍历的进阶，遍历树的时候设置双指针，pre指向当前层的最后一个节点，next指向遍历到的最新的结点，取出每层最后一个结点(pre)的值到结果数组res。

C++代码

/**
 * 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<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        
        queue<TreeNode*> que;
        que.push(root);
        TreeNode* pre = root;
        TreeNode* next = nullptr;
        while(!que.empty())
        {
            TreeNode* cur = que.front();
            que.pop();
            if(cur->left)
            {
                que.push(cur->left);
                next = cur->left;
            }
                
            if(cur->right)
            {
                que.push(cur->right);
                next = cur->right;
            }
                
            if(pre == cur)
            {
                res.push_back(cur->val);
                pre = next;
            }
        }
        
        return res;
    }
};

Python代码

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

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        res = []
        que = []
        pre = root
        nex = None
        que.append(root)
        while len(que) > 0:
            cur = que.pop(0)
            
            if cur.left:
                que.append(cur.left)
                nex = cur.left
            if cur.right:
                que.append(cur.right)
                nex = cur.right
            if cur == pre:
                pre = nex
                res.append(cur.val)
                
        return res

二叉树的锯齿层次遍历

LeetCode中文

LeetCode英文

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

解答

二叉树层序遍历的进阶，加一个标志位flag，每一层根据flag判断是否反转当前层的数组。

C++代码

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root)
            return res;
        
        queue<TreeNode*> que;
        vector<int> vec;
        que.push(root);
        TreeNode* pre = root;
        TreeNode* next = nullptr;
        bool flag = true;
        while(!que.empty())
        {
            TreeNode* cur = que.front();
            que.pop();
            vec.push_back(cur->val);
            
            if(cur->left)
            {
                que.push(cur->left);
                next = cur->left;
            }
            
            if(cur->right)
            {
                que.push(cur->right);
                next = cur->right;
            }
            
            if(cur == pre)
            {
                pre = next;
                if(!flag)
                {
                    reverse(vec.begin(),vec.end());
                }
                
                res.push_back(vec);
                vec.clear();
                flag = !flag;
            }
            
        }
        return res;
        
    }
};

Python代码

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

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        res = []
        vec = []
        que = []
        
        flag = True
        pre = root
        nex = None
        que.append(root)
        while len(que) > 0:
            cur = que.pop(0)
            vec.append(cur.val)
            
            if cur.left:
                que.append(cur.left)
                nex = cur.left
            if cur.right:
                que.append(cur.right)
                nex = cur.right
            
            if cur == pre:
                pre = nex
                if not flag:
                    vec.reverse()
                res.append(vec)
                vec = []
                flag = not flag
        
        return res

填充同一层的兄弟节点

LeetCode中文

LeetCode英文

给定一个二叉树

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

说明:

你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。

示例:

给定完美二叉树，

调用你的函数后，该完美二叉树变为：

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

解答

树的层序遍历结合链表指针操作。

C++代码

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root)
            return;
        
        bool flag = false;
        queue<TreeLinkNode*> que;
        TreeLinkNode* last = root;
        TreeLinkNode* next = nullptr;
        
        que.push(last);
        TreeLinkNode* pre = nullptr;
        TreeLinkNode* cur;
        while(!que.empty())
        {
            cur = que.front();
            que.pop();
            
            if(cur->left)
            {
                que.push(cur->left);
                next = cur->left;
            }
            
            if(cur->right)
            {
                que.push(cur->right);
                next = cur->right;
            }
           
            if(pre)
            {
                pre->next = cur;
            }
            
            pre = cur;
            
            if(cur == last)
            {
                last = next;
                pre = nullptr;
            }
        }
    }
};

Python代码

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left, right, next):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return None
        pre = root
        nex = None
        que = []
        que.append(root)
        while len(que) > 0:
            cur = que.pop(0)
            
            if cur.left:
                que.append(cur.left)
                nex = cur.left
            if cur.right:
                que.append(cur.right)
                nex = cur.right
                
            if cur == pre:
                cur.next = None
                pre = nex
            elif len(que) > 0:
                cur.next = que[0]
        
        return root

验证二叉搜索树

LeetCode中文

LeetCode英文

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解答

考察二叉树的中序遍历和链表的双指针。中序遍历二叉搜索树，设置pre和cur两个指针分别指向前一个结点和后一个节点，在中序遍历二叉树的过程中，pre和cur跟着向后移动，一旦发现 pre->val >= cur->val，则说明不是二叉搜索树；否则，便是二叉搜索树。

C++代码

/**
 * 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 Inorder(TreeNode* head)
    {
        bool left_flag = true;
        bool right_flag = true;
        if(head->left)
            left_flag = Inorder(head->left);
        
        cur = head;
        if(pre && pre->val >= cur->val)
            return false;
        
        pre = cur;
        
        if(head->right)
            right_flag = Inorder(head->right);
        
        return left_flag && right_flag;
    }
    
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        
        return Inorder(root);
    }

private:
    TreeNode* pre = nullptr;
    TreeNode* cur;
};

Python代码

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        path = []
        self.inorder(root,path)
        for i in range(1,len(path)):
            if path[i - 1] >= path[i]:
                return False
        return True
    def inorder(self,root: TreeNode,path: List[int]):
        if not root:
            return
        self.inorder(root.left,path)
        path.append(root.val)
        self.inorder(root.right,path)

路径总和II

LeetCode中文

LeetCode英文

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

解答

找出二叉树的所有路径，没经过一个节点，累加一次并且加到临时数组中。在每条路径结束的时候，判断累加的值是否和目标值相等，如果相等，则将这条路径对应的临时数组加入结果数组中；否则，继续走其他路径。找出所有路径的方法参见二叉树的所有路径。

C++代码

/**
 * 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:
    void recursion(TreeNode* root,int sum)
    {
        vec.push_back(root->val);
        if(!root->left && !root->right)
        {
            int a = accumulate(vec.begin(),vec.end(),0);
            if(a == sum)
                res.push_back(vec);
        }
        
        if(root->left)
            recursion(root->left,sum);
        
        if(root->right)
            recursion(root->right,sum);
        
        vec.pop_back();
    }
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(!root)
            return res;
        
        recursion(root,sum);
        return res;
    }
    
    private:
    vector<int> vec;
    vector<vector<int>> res;
};

Python代码

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

class Solution:
    def recursion(self,root: TreeNode,sum: int):
        if not root:
            return
        
        sum -= root.val
        self.lt.append(root.val)
        
        if not root.left and not root.right:
            if sum == 0:
                self.res.append(self.lt[:])
            self.lt.pop()
            return
        
        if root.left:
            self.recursion(root.left,sum)
        if root.right:
            self.recursion(root.right,sum)
        
        self.lt.pop()
        
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        self.res = []
        self.lt = []
        
        self.recursion(root,sum)
        
        return self.res

二叉树中的最大路径和

LeetCode中文

LeetCode英文

给定一个非空二叉树，返回其最大路径和。

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

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

解答

对于一棵root为根节点的树，假设其左子树(含左子节点)的最大路径为l_val，右子树(含右子节点)的最大路径为r_val：

如果l_val小于等于0，那么不含入左子节点（也就是说将路径从左子节点处切断），可以得到一个更大的路径；
如果r_val小于等于0，那么不含入右子节点（也就是说将路径从右子节点处切断），可以得到一个更大的路径；
如果两者都大于0，那么连通左右子树可以得到一个更大的路径。

因此，根据上面几种情况，可以得到一个局部最大的路径。局部最大是因为这个路径包含了root节点。但是全局最大的路径不一定包含root节点。因此需要一个全局最大路径的变量res，如果res小于这个局部最大路径，那么更新res。

那么l_val和r_val应该怎么得到，也就是函数应该返回什么？注意上面对l_val和r_val的描述中，这两个都包含了左右子树的根节点，因此，返回值不是res。那么是不是这个局部最大的路径？也不是，因为局部最大的路径可能连通了左右子树。因此，这个返回值是一个单边路径，也就是说，如果l_val和r_val都小于0，那么只返回根节点的值（路径只包含根节点），否则，返回l_val和r_val中较大者加上根节点的值。

/**
 * 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 maxPathSum(TreeNode* root) {
        if(!root)
            return 0;
        
        int res = INT_MIN;
        recursion(res,root);
        
        return res;
    }
    
    int recursion(int& res,TreeNode* root)
    {
        if(!root)
            return 0;
        
        int sum;
        int l_val = recursion(res,root->left);
        int r_val = recursion(res,root->right);
        
        if(l_val > 0 && r_val > 0)
        {
            sum = l_val + r_val + root->val;
        }
        else if(l_val <= 0 && r_val <= 0)
        {
            sum = root->val;
        }
        else
        {
            sum = root->val + max(l_val,r_val);
        }
        
        res = max(sum,res);
        
        if(l_val <= 0 && r_val <= 0)
            return root->val;
        else{
            int tmp = max(l_val,r_val);
            return root->val + tmp;
        }
    }
};

二叉树的中序遍历

LeetCode中文

LeetCode英文

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答

方法1：递归

C++代码

/**
 * 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:
    void recursion(TreeNode* root,vector<int>& res)
    {
        if(!root) return;
        
        recursion(root->left,res);
        res.push_back(root->val);
        recursion(root->right,res);
    }
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        recursion(root,res);
        
        return res;
    }
};

Python代码

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

class Solution:
    def recursion(self,root):
        if root is None:
            return
        self.recursion(root.left)
        self.lt.append(root.val)
        self.recursion(root.right)
        
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.lt = []
        self.recursion(root)
        return self.lt

方法2：迭代法（利用栈实现）

（1）树先一直向左走到叶节点并将沿途的结点入栈；

（2）然后向右走一步，重复第一步操作。

C++代码

/**
 * 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<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> sta;
        
        TreeNode* head = root;
        while(head || !sta.empty())
        {
            while(head)
            {
                sta.push(head);
                head = head->left;
            }
            
            head = sta.top();
            res.push_back(head->val);
            sta.pop();
            
            head = head->right;
        }
        
        return res;
    }
};

Python代码

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        sta,res = [],[]
        head = root
        while head or len(sta) > 0:
            while head:
                sta.append(head)
                head = head.left
            head = sta.pop()
            res.append(head.val)
            head = head.right
        return res

二叉搜索树中第K小的元素

LeetCode中文

LeetCode英文

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化kthSmallest 函数？

解答

中序遍历二叉搜索树，在遍历的过程中，每经过一个节点将k减1，当k == 0的时候，则找到了第k小的元素(注意边界)。

C++代码

/**
 * 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:
    void recursion(TreeNode* root,int& res,int& k)
    {
        if(!root)
            return;
        
        recursion(root->left,res,k);
        
        k--;
        if(k == 0)
        {
            res = root->val;
            return;
        }
            
        recursion(root->right,res,k);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int res;
        recursion(root,res,k);
        
        return res;
    }
};

Python代码

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

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.k = k
        self.inorder(root)
        return self.res
        
    def inorder(self,root) -> bool:
        if root is None:
            return False
        
        if self.inorder(root.left):
            return True
            
        self.k -= 1
        if self.k == 0:
            self.res = root.val
            return True
            
        if self.inorder(root.right):
            return True
        
        return False

二叉树的前序遍历

LeetCode中文

LeetCode英文

给定一个二叉树，返回它的前序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答

方法1：递归

C++代码

/**
 * 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:
    void preorder(TreeNode* root,vector<int>& vec)
    {
        if(!root) return;
        
        vec.push_back(root->val);
        preorder(root->left,vec);
        preorder(root->right,vec);
    }
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root,res);
        return res;
    }
};

Python代码

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.preOrder(root,res)
        return res
    
    def preOrder(self,root,lt: List[int]):
        if root is None:
            return
        
        lt.append(root.val)
        
        self.preOrder(root.left,lt)
        self.preOrder(root.right,lt)

方法2：迭代

思路：对每个结点按照 根->右->左 的顺序入栈，出栈的顺序就是前序遍历的结果。

C++代码

/**
 * 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<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return vector<int>();
        
        vector<int> res;
        stack<TreeNode*> sta;
        sta.push(root);
        while(!sta.empty())
        {
            TreeNode* head = sta.top();
            sta.pop();
            res.push_back(head->val);
            
            if(head->right)
                sta.push(head->right);
            if(head->left)
                sta.push(head->left);
        }
        
        return res;
    }
};

Python代码

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []
        sta = []
        res = []
        sta.append(root)
        while len(sta) > 0:
            tmp = sta.pop()
            res.append(tmp.val)
            
            if tmp.right:
                sta.append(tmp.right)
            if tmp.left:
                sta.append(tmp.left)
        return res

具有所有最深结点的最小子树

LeetCode中文

LeetCode英文

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。

如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。

一个结点的子树是该结点加上它的所有后代的集合。

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

示例：

输入：[3,5,1,6,2,0,8,null,null,7,4]

输出：[2,7,4]

解释：

我们返回值为 2 的结点，在图中用黄色标记。

在图中用蓝色标记的是树的最深的结点。

输入 "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" 是对给定的树的序列化表述。输出 "[2, 7, 4]" 是对根结点的值为 2 的子树的序列化表述。输入和输出都具有 TreeNode 类型。

解答

解读题意：得到的子树必须包含所有最深的结点且子树的总结点数最少，然后返回这个子树的根节点。

后序遍历二叉树的每个节点，得到左右子树的深度。

在递归函数中，对每个子树的处理分三种情况：

如果 左子树深度 == 右子树深度，则返回当前节点；
如果 左子树深度 > 右子树深度，返回左结点；
如果 左子树深度 < 右子树深度，返回右深度。

最后，就能得到满足条件的那个根节点。

/**
 * 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* subtreeWithAllDeepest(TreeNode* root) {
        if(!root) return nullptr;
        
        int dep = 0;
        return recursion(dep,root);
    }
    
    TreeNode* recursion(int& depth,TreeNode* root)
    {
        if(!root->left && !root->right)
        {
            depth = 1;
            return root;
        }
        
        int l_dep = 0,r_dep = 0;
        TreeNode *l_root = nullptr,*r_root = nullptr;
        if(root->left)
        {
            l_root = recursion(l_dep,root->left);
        }
        
        if(root->right)
        {
            r_root = recursion(r_dep,root->right);
        }
        
        depth = max(l_dep,r_dep) + 1;
        
        if(l_dep == r_dep)
        {
            return root;
        }
        else if(l_dep > r_dep)
        {
            return l_root;
        }
        else
            return r_root;
        
    }
};

二叉树的后序遍历

LeetCode中文

LeetCode英文

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答

方法1：递归

/**
 * 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:
    void recursion(TreeNode* root,vector<int>& res)
    {
        if(!root) return;
        
        recursion(root->left,res);
        recursion(root->right,res);
        res.push_back(root->val);
    }
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        
        recursion(root,res);
        
        return res;
    }
};

方法2：迭代

利用栈实现，先按照 中->右->左 的顺序遍历树并放入栈中（方法类似前序遍历中->左->右），然后将栈的数据转移到另一个栈中，遍历顺序就变成 左->右->中（后序顺序）。

/**
 * 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<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return vector<int>();
        
        vector<int> res;
        stack<TreeNode*> sta1,sta2;
        sta1.push(root);
        while(!sta1.empty())
        {
            TreeNode* cur = sta1.top();
            sta1.pop();
            sta2.push(cur);
            if(cur->left)
                sta1.push(cur->left);
            if(cur->right)
                sta1.push(cur->right);
        }
        
        while(!sta2.empty())
        {
            TreeNode* cur = sta2.top();
            sta2.pop();
            res.push_back(cur->val);
        }
        
        return res;
    }
};

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

LeetCode中文

LeetCode英文

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

解答

考察二叉树的遍历(自选一种遍历顺序)，同时结合了字符串的处理，边界条件和特殊情况要考虑清楚。

/**
 * 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:
    void ser(TreeNode* root,string& str)
    {
        if(!root)
        {
            str += "null,";
            return;
        }
            
        stringstream stream;
        stream<<root->val;
        str += stream.str();
        str += ',';
        
        ser(root->left,str);
        ser(root->right,str);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        if(!root)
            return res;
        
        ser(root,res);
        return res;
    }

    void des(string& str,TreeNode*& root,int& index)
    {
        if(index >= str.size() - 1)
            return;
        
        if(str[index] == 'n')
        {
            root = nullptr;
            while(str[index++] != ',');
            
            return;
        }
        
        int num = 0;
        int flag = 1;
        
        if(str[index] == '-')
        {
            flag = -1;
            index++;
        }
        
        while(index < str.size() && str[index] != ',')
        {
            num=(10 * num + (str[index] - '0')) * flag;
            index++;
        }
        
        
        root=new TreeNode(num);
        if(index == str.size())
            return;
        else
            index++;
        
        des(str,root->left,index);
        des(str,root->right,index);
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;
        
        int index = 0;
        TreeNode* res = nullptr;
        des(data,res,index);
        return res;
    }
};

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

Files

二叉树.md

Latest commit

History

二叉树.md

File metadata and controls

二叉树总结

二叉树的最大深度

解答

合并二叉树

解答

将有序数组转换为二叉搜索树

解答

二叉树的所有路径

解答

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

解答

方法1

平衡二叉树

解答

对称二叉树

解答

二叉树的最近公共祖先

解答

方法1

方法2

从前序与中序遍历序列构造二叉树

解答

求根到叶子节点数字之和

解答

二叉树的层次遍历

解答

二叉树的右视图

解答

二叉树的锯齿层次遍历

解答

填充同一层的兄弟节点

解答

验证二叉搜索树

解答

路径总和II

解答

二叉树中的最大路径和

解答

二叉树的中序遍历

解答

方法1：递归

方法2：迭代法（利用栈实现）

二叉搜索树中第K小的元素

解答

二叉树的前序遍历

解答

方法1：递归

方法2：迭代

具有所有最深结点的最小子树

解答

二叉树的后序遍历

解答

方法1：递归

方法2：迭代

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

解答