leetcode Tree 整理版

本次题解为 leetcode tree 的整理，包括

依照leetcode定义自己写的createTree方法，便于测试中序遍历的下标和
94 Binary Tree Inorder Traversal
95 Unique Binary Search Trees II
96 Unique Binary Search Trees
98 Validate Binary Search Tree
99 Recover Binary Search Tree
100 Same Tree
101 Symmetric Tree
102 Binary Tree Level Order Traversal
103 Binary Tree Zigzag Level Order Traversal
104 Maximum Depth of Binary Tree
105 Construct Binary Tree from Preorder and Inorder Traversal
106 Construct Binary Tree from Inorder and Postorder Traversal
107 Binary Tree Level Order Traversal II
108 Convert Sorted Array to Binary Search Tree
109 Convert Sorted List to Binary Search Tree
110 Balanced Binary Tree
111 Minimum Depth of Binary Tree
112 Path Sum
113 Path Sum II
114 Flatten Binary Tree to Linked List
116 Populating Next Right Pointers in Each Node
117 Populating Next Right Pointers in Each Node II
124 Binary Tree Maximum Path Sum
129 Sum Root to Leaf Numbers
144 Binary Tree Preorder Traversal
145 Binary Tree Postorder Traversal
173 Binary Search Tree Iterator
199 Binary Tree Right Side View
222 Count Complete Tree Nodes
226 Invert Binary Tree
230 Kth Smallest Element in a BST
235 Lowest Common Ancestor of a Binary Search Tree
236 Lowest Common Ancestor of a Binary Tree
257 Binary Tree Paths
297 Serialize and Deserialize Binary Tree
449. Serialize and Deserialize BST

1.首先是leetcode对于树的表示方法：

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:
1
2
3
4
5
6
7
  1
 / \
2   3
   /
  4
   \
    5
The above binary tree is serialized as "{1,2,3,null,null,4,null,null,5}".

树结点表示为：

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

我的建树方法见297题 Serialize and Deserialize Binary Tree的方法一

2.题解归类

1.构建树

用前序和中序建树105
用后序和中序建树106
数组构建BST 108
链表构建BST 109

2.树的遍历

前序 144
中序 94
后序 145
层次 102 103 107

3.树的属性

求深度 104
是否平衡是平衡树 110
最小深度 111

4.BST树

判断BST是否合法 98
恢复BST 99
BST实现迭代：173（用到某一遍历）

3.题解代码（按题号顺序）

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},
1
2
3
4
5
6
1
 \
  2
 /
3
return [1,3,2].

题目地址:leetcode 94 Binary Tree Inorder Traversal

题意：给定一棵树，求它的中序遍历。

思路：中序遍历和前序、后序不同地方在于是先输出左子结点然后根结点，最后右子结点。

递归版本很好理解。

非递归版本先将所有左子树入栈，之后将所有右子树的左子树入栈。（看代码吧~）

Python

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        ans=[]
        self.dfs(root,ans)
        return ans

    def dfs(self,root,ans):
        if not root : return
        self.dfs(root.left,ans)
        ans.append(root.val)
        self.dfs(root.right,ans)

Python非递归版本

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def inorderTraversal(self, root):
        if not root: return []
        ans,q=[],[]
        self.allLeftIntoStack(root,q)
        while q:
            t=q.pop()
            ans.append(t.val)
            if t.right:self.allLeftIntoStack(t.right,q)

        return ans

    def allLeftIntoStack(self,root,q):
        while root:
            q.append(root)
            root=root.left

95. Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1..._n_.

For example, Given n = 3, your program should return all 5 unique BST's shown below.
1
2
3
4
5
6
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

题目地址：leetcode Unique Binary Search Trees II

题目大意：给定n，求1~n共n个数，能组成几棵不一样的BST，建立这些树并且返回所有不同BST的根结点。

思路：

分治，对于1_{n这n个数，都有可能成为根结点。枚举1}n，对于 1<=i<=n，有i的左结点为[1,i-1] (i-1 >=1),右结点是[i+1,n] i+1 <=n

递归的获取左右子结点，然后只需要建立根结点，使根结点的左右子结点指向获取的左右子结点即可。

C++

class Solution {
	vector<TreeNode*> build(int s, int e) {
		vector<TreeNode*> ans;
		if (s > e) {
			ans.push_back(nullptr);
			return ans;
		}

		for (int k = s; k <= e; ++k) {
			vector<TreeNode*> left = build(s, k - 1);
			vector<TreeNode*> right = build(k + 1, e);
			for (int i = 0; i < left.size(); ++i) {
				for (int j = 0; j < right.size(); ++j) {
					TreeNode *root = new TreeNode(k);
					root->left = left[i];
					root->right = right[j];
					ans.push_back(root);
				}
			}
		}
		return ans;
	}

public:
	vector<TreeNode*> generateTrees(int n) {
		return n >= 1 ? build(1, n) : vector<TreeNode *>();
	}
};

Python

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        return self.dfs(1, n) if n >= 1 else []

    def dfs(self, s, e):
        if s > e: return [None]
        ans = []
        for i in range(s, e + 1):
            L = self.dfs(s, i - 1)
            R = self.dfs(i + 1, e)
            for left in L:
                for right in R:
                    root = TreeNode(i)
                    root.left, root.right = left, right
                    ans.append(root)
        return ans

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1..._n_?

For example, Given n = 3, there are a total of 5 unique BST's.
1
2
3
4
5
6
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

题目大意：给定n，求1~n共n个数，能组成几棵不一样的BST

思路：

可以类似95题写dfs+记忆化搜索

class Solution {
	int dfs(int n, vector<int> &dp) {
		if (n == 0) return 0;
		if (n == 1) return 1;
		if (dp[n] != -1) return dp[n];
		int cnt = 0;
		for (int k = 1; k <= n; ++k) {
			int left = dfs(k - 1, dp);
			int right = dfs(n - k, dp);
			if (left == 0) cnt += right;
			else if (right == 0) cnt += left;
			else cnt += right * left;
		}
		return dp[n] = cnt;
	}
public:
	int numTrees(int n) {
		vector<int> dp(n + 1, -1);
		return dfs(n, dp);
	}
};

也可以写成非递归的形式：

设dp[n]为n个数组成的不同BST总数。

如果左儿子个数为j，有儿子显然为n-1-j个，那么总共显然有 dp[j] * dp[n-1-j]种

故枚举j从0~n-1然后相加既可。

C++

class Solution {
public:
	int numTrees(int n) {
		vector<int> dp(n + 1, 0);
		dp[0] = 1;
		for (int i = 1; i <= n; ++i)
			for (int j = 0; j < i; ++j)
				dp[i] += dp[j] * dp[i - j - 1];
		return dp[n];
	}
};

Python

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - 1 - j]
        return dp[n]

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

题目地址：leetcode 98 Validate Binary Search Tree

题意：给定一棵BST，判断其是否合法。合法需要满足：

根结点大于左子树结点，根结点小于右子树结点。
左右子树是合法的BST

思路:

递归判断左右子树。需要用出现过的最大、最小值来判断。如左子树最大值不可能超过根，右子树最小值不可能小于根
中序遍历。合法的BST中序遍历必为有序序列。

方法一

C++

class Solution {
    bool dfs(TreeNode *root, long min_v, long max_v){
        if(!root) return true;
        if(root->val <= min_v  root->val >= max_v)
            return false;
        return dfs(root->left, min_v, root->val) && dfs(root->right, root->val, max_v);
    }
    
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root, LONG_MIN, LONG_MAX);
    }
};

Python

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isValidBST(self, root):
        INF = float('inf')
        return self.judge(root,-INF,INF)
    def judge(self,root,minV,maxV):
        if not root: return True   
        if root.val <= minV or root.val >= maxV: return False      
        return self.judge(root.left,minV,root.val) and \
            self.judge(root.right,root.val,maxV)

方法二

C++

class Solution {
    bool dfs(TreeNode *root, TreeNode * &pre){
        if(!root) return true;
        bool left = dfs(root->left, pre);
        if(!left  pre && pre->val >= root->val)
            return false;
        pre = root;
        return dfs(root->right, pre);            
    }
    
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre = nullptr;
        return dfs(root, pre);
    }
};

Python

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        pre = [None]
        return self.dfs(root, pre)
    
    def dfs(self, root, pre):
        if not root: return True
        if not self.dfs(root.left, pre) or pre[0] and root.val <= pre[0].val:
            return False
        pre[0] = root
        return self.dfs(root.right, pre)

99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

题目地址：leetcode 99 Recover Binary Search Tree

题意：一棵BST中有两个元素被调换了，求在不破坏BST情况下，将其恢复。

思路：对于此问题，关键是要找到被调换的两个元素。我们知道，对于中序遍历，合法的BST数必为有序，故进行中序遍历，如果pre.val >root.val说明有误。注意区分第一次和第二次，标记即可。

C++

class Solution {
    void dfs(TreeNode *root, TreeNode *&pre, TreeNode *&first, TreeNode *&second){
        if(!root)  return;
        dfs(root->left, pre, first, second);
        if(pre && root->val <= pre->val){
            if(!first)  first = pre;
            second = root;
        }
        pre = root;
        dfs(root->right, pre, first, second);
    }
    
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *pre = nullptr;
        dfs(root, pre, first, second);
        swap(first->val, second->val);
    }
};

Python

class Solution:
    # @param root, a tree node
    # @return a tree node
    def recoverTree(self, root):
        self.pre,self.first,self.second=None,None,None
        self.dfs(root)
        t=self.first.val
        self.first.val,self.second.val = self.second.val,t
        return root

    def dfs(self,root):
        if not root: return
        if root.left:  self.dfs(root.left)
        
        if self.pre:
            if self.pre.val > root.val : 
                if not self.first :self.first,self.second=self.pre,root
                else:   self.second=root

        self.pre=root
        if root.right: self.dfs(root.right)

100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

题目地址：leetcode Same Tree

题目大意：给定两棵树，判断他们是否相等（结构和值都相等）

思路：递归判断即可。

C++

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

Python

class Solution:
    # @param p, a tree node
    # @param q, a tree node
    # @return a boolean
    def isSameTree(self, p, q):
        if not p and not q: return True
        if p and q:
            return p.val==q.val and self.isSameTree(p.left,q.left) \
                and self.isSameTree(p.right,q.right)
        return False

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:
1
2
3
4
5
6
    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
1
2
3
4
5
6
  1
 / \
2   2
 \   \
 3    3
Note: Bonus points if you could solve it both recursively and iteratively.

题目地址：leetcode Symmetric Tree

题目大意：给定一棵树，判断它是否关于root对称。

思路：继续递归吧。。。水

C++

class Solution {
    bool dfs(TreeNode* t1, TreeNode* t2) {
        if (!t1 && !t2) return true;
        if (!t1 && t2 || t1 && !t2) return false;
        if (t1->val != t2->val) return false;
        return dfs(t1->left, t2->right) && dfs(t1->right, t2->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        return !root || dfs(root->left, root->right);
    }
};

Python

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        if not root: return True
        return self.judge(root.left,root.right)

    def judge(self,L,R):
        if not L and not R: return True
        if L and R:
            return L.val==R.val and self.judge(L.left,R.right) \
            and self.judge(L.right,R.left)
        return False

还可以用BFS的方式做：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        vector<TreeNode *> cur_level{root->left, root->right};
        
        while(!cur_level.empty()){
            int n = cur_level.size();
            for(int i = 0, j = n - 1; i < j; ++i, --j){
                TreeNode *a = cur_level[i];
                TreeNode *b = cur_level[j];
                if(!a && b  a && !b) return false;
                if(a && b && a->val != b->val) return false;
            }
            vector<TreeNode *> next_level;
            for(int i = 0; i < n; ++i){
                if(!cur_level[i]) continue;
                next_level.push_back(cur_level[i]->left);
                next_level.push_back(cur_level[i]->right);
            }
            cur_level = next_level;
        }
        return true;
    }
};

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree {3,9,20,#,#,15,7},
1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7
return its level order traversal as:
1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

题目地址：leetcode Binary Tree Level Order Traversal

题目大意：给定一棵树，返回其层次遍历

思路：

方法一: 用队列进行层次遍历

C++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            vector<int> cur_level;
            int n = q.size();
            while(n--){
                TreeNode *cur = q.front();
                q.pop();
                cur_level.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            ans.push_back(cur_level);
        }
        return ans;
    }
};

Python

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        q, ans = collections.deque([root]), []
        while q:
            cur_level = []
            n = len(q)
            for _ in range(n):
                cur = q.popleft()
                cur_level.append(cur.val)
                if cur.left: q.append(cur.left)
                if cur.right: q.append(cur.right)
            ans.append(cur_level)
        return ans

方法二先序遍历

class Solution {
    void dfs(int h, TreeNode *root, vector<vector<int>> &ans){
        if(!root) return;
        if(h >= ans.size())
            ans.push_back(vector<int>{});
        ans[h].push_back(root->val);
        dfs(h + 1, root->left, ans);
        dfs(h + 1, root->right, ans);
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(0, root, ans);
        return ans;
    }
};

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree {3,9,20,#,#,15,7},
1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7
return its zigzag level order traversal as:
1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

题目地址：leetcode Binary Tree Zigzag Level Order Traversal

题目大意：给定一棵树，返回其层次遍历（要求第一行从左到右，第二行从右到左）

思路：和上面一题差不多，加个判断奇偶即可。

C++

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode *> q;
        q.push(root);
        for(int level = 0; !q.empty(); ++level){
            int t = q.size();
            vector<int> cur_level;
            for(int i = 0; i < t; ++i){
                TreeNode *cur = q.front();
                q.pop();
                cur_level.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            if(level & 1)
                reverse(cur_level.begin(), cur_level.end());
            ans.push_back(cur_level);
        }
        return ans;
    }
};

Python

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        q = collections.deque([root])
        ans = []
        level = 0
        while q:
            cur_level = []
            cur_size = len(q)
            for i in range(cur_size):
                cur = q.popleft()
                if cur.left: q.append(cur.left)
                if cur.right: q.append(cur.right)
                cur_level.append(cur.val)
            ans.append(cur_level[::-1] if level & 1 else cur_level)
            level += 1
        return ans

当然还可以不逆序，直接输出到对应位置

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        q = collections.deque([root])
        ans = []
        level = 0
        while q:
            cur_size = len(q)
            cur_level = [0] * cur_size
            for i in range(cur_size):
                cur = q.popleft()
                if cur.left: q.append(cur.left)
                if cur.right: q.append(cur.right)
                index = (cur_size - i - 1) if level & 1 else i
                cur_level[index] = cur.val
            ans.append(cur_level)
            level += 1
        return ans

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

题目地址：leetcode Maximum Depth of Binary Tree

题目大意：给定一棵树，返回其最大深度。

思路：思路，dfs.

C++

class Solution {
    void dfs(int cur, int &max_depth, TreeNode *root){
        if(!root) return;
        if(++cur > max_depth)
            max_depth = cur;
        
        dfs(cur, max_depth, root->left);
        dfs(cur, max_depth, root->right);
        
    }
public:
    int maxDepth(TreeNode* root) {
        int ans = 0;
        dfs(0, ans, root);
        return ans;
    }
};

另一种更简洁写法

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

Python

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

105 . Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

题目地址：leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

题意：给定一棵树的前序和中序遍历，构建这棵树

思路：以下面的例子为例：

前序遍历为： 3,9,20,15,7

中序遍历为： 9,3,15,20,7

前序遍历的第一个一定是根结点，而中序遍历的根结点把树准确的分为左子树和右子树。

所以，在中序遍历中查找3，发现下标为1，那么[0,1)为左子树，[2,5)为右子树。

递归的往下查找即可。

可以写出简洁的code

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder: return None
        root = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1: index + 1], inorder[:index])
        root.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return root

不过这样每次都需要切片，效率比较低。

我们可以设前序遍历开始为pb,结束pe，中序遍历开始为ib,结束为ie。前序遍历的第pb个元素（即当前根结点）在中序遍历中下标为index

则长度为len = index - ib

那么有，

左子树，每次递归的下标为：[pb + 1, pb + len + 1) [ ib, ib+len)
右子树：[pb + len + 1, pe) [ib + len + 1, ie)

Python

class Solution(object):
    def _build(self, pb, pe, ib, ie, preorder, inorder):
        if pb >= pe or ib >= ie: return None
        root = TreeNode(preorder[pb])
        len_left = inorder.index(preorder[pb]) - ib
        root.left = self._build(pb + 1, pb + len_left + 1, ib, ib + len_left, preorder, inorder)
        root.right = self._build(pb + len_left + 1, pe, ib + len_left + 1, ie, preorder, inorder)
        return root
        
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        return self._build(0, len(preorder), 0, len(inorder), preorder, inorder)

C++

class Solution {
    TreeNode* build(int pb, int pe, int ib, int ie, const vector<int>& preorder, const vector<int>& inorder){
        if(pb >= pe || ib >= ie) return nullptr;
        TreeNode *root = new TreeNode(preorder[pb]);
        int len = find(inorder.begin() + ib, inorder.begin() + ie, preorder[pb]) - inorder.begin() - ib;
        root->left = build(pb + 1, pb + len + 1, ib, ib + len, preorder, inorder);
        root->right = build(pb + len + 1, pe, ib + len + 1, ie, preorder, inorder);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
        return build(0, preorder.size(), 0, inorder.size(), preorder, inorder);
    }
};

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

题目地址：leetcode 106 Construct Binary Tree from Inorder and Postorder Traversal

题意：给定一棵树的中序和后序遍历，构建这棵树。

思路：

思路：以下面的例子为例：

后序遍历为： 9,15,7,20,3

中序遍历为： 9,3,15,20,7

后序遍历的最后一个一定是根结点，而中序遍历的根结点把树准确的分为左子树和右子树。

和105题差不多，简单的写有：

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder:
            return None
        root = TreeNode(postorder[-1])
        index = inorder.index(postorder[-1])
        root.left = self.buildTree(inorder[:index], postorder[:index])
        root.right = self.buildTree(inorder[index + 1:], postorder[index:len(postorder) -1])
        return root

我们可以设后序遍历开始为pb,结束pe，中序遍历开始为ib,结束为ie。前序遍历的第pb个元素（即当前根结点）在中序遍历中下标为index

则长度为len = index - ib

那么有，

左子树，每次递归的下标为：[pb, pb + len) [ ib, ib+len)
右子树：[pb + len, pe - 1) [ib + len + 1, ie)

可以看出中序遍历的下标和上面一题是一样的

Python

这里用hash表存下了下标，这样每次不用find或者index查找了，比较快

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        index_dict = {val : i for i, val in enumerate(inorder)}
        return self.create(inorder, postorder, index_dict, 0, len(inorder), 0, len(postorder))

    def create(self, inorder: List[int], postorder: List[int], index_dict: dict, ib: int, ie: int, pb: int, pe: int) -> TreeNode: 
        if ib >= ie or pb >= pe:
            return None
        root = TreeNode(postorder[pe - 1])
        index = index_dict[root.val]
        left_len = index - ib
        root.left = self.create(inorder, postorder, index_dict, ib, ib + left_len, pb, pb + left_len)
        root.right = self.create(inorder, postorder, index_dict, ib + left_len + 1, ie, pb + left_len, pe - 1)
        return root

C++

class Solution {
    TreeNode* build(int is, int ie, int ps, int pe, const vector<int>& inorder, const vector<int>& postorder) {
        if(is >= ie  ps >= pe) return nullptr;
        TreeNode *root = new TreeNode(postorder[pe - 1]);
        int len = find(inorder.begin() + is, inorder.begin() + ie, postorder[pe - 1]) - inorder.begin() - is;
        root->left = build(is, is + len, ps, ps + len, inorder, postorder);
        root->right = build(is + len + 1, ie, ps + len, pe - 1, inorder, postorder);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return build(0, inorder.size(), 0, postorder.size(), inorder, postorder);
    }
};

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree {3,9,20,#,#,15,7},
1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7
return its bottom-up level order traversal as:
1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

题目地址：leetcode Binary Tree Level Order Traversal II

题目大意：给定一棵树，返回其层次遍历的逆序。

思路：和102题其实一样，最后结果逆序即可。太水了

C++

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            int pre_size = q.size();
            vector<int> cur_level;
            for(int i = 0; i < pre_size; ++i){
                TreeNode *cur = q.front();
                q.pop();
                cur_level.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            ans.push_back(cur_level);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Python

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return [] 
        q, ans = collections.deque([root]), [] 
        while q: 
            cur_level = [] 
            n = len(q) 
            for _ in range(n): 
                cur = q.popleft() 
                cur_level.append(cur.val) 
                if cur.left: 
                    q.append(cur.left) 
                if cur.right: 
                    q.append(cur.right) 
            ans.append(cur_level) 
        return ans[::-1]

还可以DFS做

class Solution {
    void dfs(int level, TreeNode* root, vector<vector<int>> &ans){
        if(!root) return;
        if(level >= ans.size())
            ans.push_back(vector<int>{});
        
        ans[level].push_back(root->val);
        dfs(level + 1, root->left, ans);
        dfs(level + 1, root->right, ans);
    }
    
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(0, root, ans);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

108. Convert Sorted Array to Binary Search Tree

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

题目地址：leetcode 108 Convert Sorted Array to Binary Search Tree

题意：给定一个排好序的数组，要求建造BST树（高度要平衡）

思路：每次二分，递归建立左右子树

C++

class Solution {
private:
	TreeNode* BuildTree(int L, int R, const vector<int>& nums) {
		if (L > R) return nullptr;
		int mid = L + ((R - L) >> 1);
		TreeNode *root = new TreeNode(nums[mid]);
		root->left = BuildTree(L, mid - 1, nums);
		root->right = BuildTree(mid + 1, R, nums);
		return root;
	}

public:
	TreeNode* sortedArrayToBST(vector<int>& nums) {
		return BuildTree(0, nums.size() - 1, nums);
	}
};

Java

class Solution {
    private TreeNode BuildTree(int L, int R, final int[] nums) {
        if (L > R) return null;
        int mid = L + ((R - L) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = BuildTree(L, mid - 1, nums);
        root.right = BuildTree(mid + 1, R, nums);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return BuildTree(0, nums.length - 1, nums);
    }
}

Python

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        def build_tree(L, R):
            if L > R: return None
            mid = (L + R) >> 1
            root = TreeNode(nums[mid])
            root.left = build_tree(L, mid - 1)
            root.right = build_tree(mid + 1, R)
            return root

        return build_tree(0, len(nums) - 1)

109 Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

题目地址：leetcode 109 Convert Sorted List to Binary Search Tree

题意：给定一个排好序的链表，要求建造BST树（高度要平衡）

思路：

方法一

每次将链表分为左右两部分即可。

使用快慢指针
复杂度O(nlogn)

C++

class Solution {
	TreeNode* createTree(ListNode* head, ListNode* end) {
		if (head == end) return nullptr;
		ListNode *fast = head, *slow = head;
		while (fast != end && fast->next != end) {
			slow = slow->next;
			fast = fast->next->next;
		}
		TreeNode *root = new TreeNode(slow->val);
		root->left = createTree(head, slow);
		root->right = createTree(slow->next, end);
		return root;
	}
public:
	TreeNode* sortedListToBST(ListNode* head) {
		return createTree(head, nullptr);
	}
};

Java

class Solution {
    private TreeNode buildTree(ListNode head, ListNode end) {
        if (head == end) return null;
        ListNode slow = head, fast = head;
        while (fast != end && fast.next != end) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = buildTree(head, slow);
        root.right = buildTree(slow.next, end);
        return root;
    }

    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head,null);
    }
}

Python

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """

        def build_tree(head, end):
            if head == end: return None
            fast = slow = head
            while fast != end and fast.next != end:
                slow, fast = slow.next, fast.next.next
            root = TreeNode(slow.val)
            root.left = build_tree(head, slow)
            root.right = build_tree(slow.next, end)
            return root

        return build_tree(head, None)

之前的python，计数的，不如快慢指针优雅。

class Solution:
    # @param head, a list node
    # @return a tree node
    def sortedListToBST(self, head):
        if not head: return None
        tail ,length =head ,0
        while tail: tail,length=tail.next,length+1
        return self.dfs(head,0,length-1)

    def dfs(self,head,L,R):
        if L == R : return TreeNode(head.val)
        if L >  R : return None
        mid ,cnt ,tmp= (L+R)>>1,L,head
        while cnt < mid: cnt , tmp = cnt + 1,tmp.next
        root = TreeNode(tmp.val)
        root.left,root.right=self.dfs(head,L,mid-1),self.dfs(tmp.next,mid+1,R)
        return root

方法二

BST利用中序遍历为有序的性质，来建树。

相当于链表保存的为中序遍历
要让建出来的树尽可能的平衡，那么用二分，mid = (L + R)/2，左边的就是[L,mid-1]，右边[mid+1,R]
中序遍历先遍历左子树，保存全局的链表head指针，每次向后移动即可。

C++

class Solution {
private:
	ListNode *head;

	TreeNode* inorderBuildTree(int L, int R) {
		if (L > R) return nullptr;
		int mid = L + ((R - L) >> 1);
		TreeNode *left = inorderBuildTree(L, mid - 1);
		TreeNode *root = new TreeNode(head->val);
		head = head->next;
		root->left = left;
		root->right = inorderBuildTree(mid + 1,R);
		return root;
	}

public:
	TreeNode* sortedListToBST(ListNode* head) {
		int n = 0;
		this->head = head;
		for (; head; head = head->next) n++;
		return inorderBuildTree(0, n - 1);
	}
};

Java

class Solution {
    private ListNode head = null;

    private TreeNode inorderBuildTree(int L, int R) {
        if (L > R) return null;
        int mid = L + ((R - L) >> 1);
        TreeNode left = inorderBuildTree(L, mid - 1);
        TreeNode root = new TreeNode(head.val);
        head = head.next;
        root.left = left;
        root.right = inorderBuildTree(mid + 1, R);
        return root;
    }

    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        this.head = head;
        for (; head != null; head = head.next) n++;
        return inorderBuildTree(0, n - 1);
    }
}

Python

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """

        def inorder_build_tree(L, R):
            if L > R: return None
            mid = (L + R) >> 1
            left = inorder_build_tree(L, mid - 1)
            root = TreeNode(self.head.val)
            self.head = self.head.next
            root.left = left
            root.right = inorder_build_tree(mid + 1, R)
            return root

        p = self.head = head
        n = 0
        while p:
            n += 1
            p = p.next
        return inorder_build_tree(0, n - 1)

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

题目地址：leetcode Balanced Binary Tree

题目大意：给定一棵树，判断其是否是平衡树（要求左右子树高度差不能超过1）

思路：用DFS来计算高度，若高度差超过1，则返回-1.否则，返回高度。

C++

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

Python

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.dfs(root) != -1

    def dfs(self, root):
        if not root: return 0
        left, right = self.dfs(root.left), self.dfs(root.right)
        if left < 0 or right < 0 or abs(left - right) >1 :
            return -1
        return max(left, right) + 1

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

题目地址：leetcode Minimum Depth of Binary Tree

题目大意：给定二叉树，求其最小的高度。（从根结点到叶结点的距离）

思路：DFS。注意叶结点的判断。

C++

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

Python

class Solution:
    # @param root, a tree node
    # @return an integer
    def minDepth(self, root):
        if not root : return 0
        return self.dfs(root,0)

    def dfs(self,root,depth):
        if not root : return depth
        if not root.left and root.right: return self.dfs(root.right,depth+1)
        if root.left and not root.right: return self.dfs(root.left,depth+1)
        if not root.left and not root.right: return depth + 1
        L , R = self.dfs(root.left,depth+1),self.dfs(root.right,depth+1)    
        return min(L,R)

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example: Given the below binary tree and sum = 22,
1
2
3
4
5
6
7
8
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

题目地址：leetcode Path Sum

题目大意：给定一棵树，判断是否有从根结点到叶结点和为sum的情况。

思路：继续深搜。。

C++

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        sum -= root->val;
        if(!root->left && !root->right)
            return sum == 0;
        return hasPathSum(root->left, sum )  hasPathSum(root->right, sum);
    }
};

Python

class Solution(object):
    def hasPathSum(self, root, target):
        """
        :type root: TreeNode
        :type target: int
        :rtype: bool
        """
        if not root: return False
        target -= root.val
        if not root.left and not root.right:
            return target == 0
        return self.hasPathSum(root.left, target) or self.hasPathSum(root.right, target)

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example: Given the below binary tree and sum = 22,
1
2
3
4
5
6
7
8
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
return
1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

题目地址：leetcode Path Sum II

题目大意：给定二叉树，要求返回其和为sum的所有路径

思路：DFS。。。

C++

class Solution {
    void dfs(vector<int> &cur, TreeNode *root, int sum, vector<vector<int>> &ans){
        if(!root)
            return;
        
        cur.push_back(root->val);
        sum -= root->val;
        if(!root->left && !root->right && sum == 0)
            ans.push_back(cur);
        
        dfs(cur, root->left, sum, ans);
        dfs(cur, root->right, sum, ans);
        cur.pop_back();
    }
    
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ans;
        vector<int> cur;
        dfs(cur, root, sum, ans);
        return ans;
    }
};

Python

class Solution:
    def dfs(self, cur, cur_sum, root, target, ans):
        if not root:
            return
        
        cur_sum += root.val
        cur.append(root.val)
        if cur_sum == target and not root.left and not root.right:
            ans.append(cur[:])
        else:
            self.dfs(cur, cur_sum, root.left, target, ans)
            self.dfs(cur, cur_sum, root.right, target, ans)
        cur.pop()

    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        ans = []
        cur = []
        self.dfs(cur, 0, root, target, ans)
        return ans

也可以这么写

class Solution:
    # @param root, a tree node
    # @param sum, an integer
    # @return a list of lists of integers
    def pathSum(self, root, sum):
        if not root:return []
        ans ,path=[] ,[root.val]
        self.dfs(root.val,root,sum,path,ans)
        return ans

    def dfs(self,cur,root,sum,path,ans):       
        if not root.left and not root.right: #leaf
            if cur == sum:
                ans.append(path[:])
            return

        if root.left:
            path.append(root.left.val)  
            self.dfs(cur+root.left.val,root.left,sum,path,ans)
            path.pop()

        if root.right:
            path.append(root.right.val)  
            self.dfs(cur+root.right.val,root.right,sum,path,ans)
            path.pop()

114. Flatten Binary Tree to Linked List

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

For example, Given
1
2
3
4
5
6
    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:
1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

题目地址：leetcode Flatten Binary Tree to Linked List

题目大意：给定一棵二叉树，要求将其变为一条链（按照前序遍历的顺序）

思路：递归，设root左右子结点为L和R，把L和R分别变为链，L最后一个元素指向R即可。

C++

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

Python

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        self.flatten(root.left)
        self.flatten(root.right)
        left = root.left
        if not left: return
        while left.right:
            left = left.right
        left.right = root.right
        root.right = root.left
        root.left = None

116. 117 Populating Next Right Pointers in Each Node

Given a binary tree
1
2
3
4
5
6
struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example, Given the following perfect binary tree,
1
2
3
4
5
6
     1
   /  \
  2    3
 / \  / \
4  5  6  7
After calling your function, the tree should look like:
1
2
3
4
5
     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

题目地址：

题意：给定一棵树，要求将其每一层的子结点连接起来。

思路：117比116的区别在于，116是满二叉树，117不一定。

一个思路是层次遍历，这样不管是不是满二叉树，都不会错，但是空间并不是O(1)的

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        if not root:return
        pre,q=[],[]
        pre.append(root)
        while pre:
            n = len(pre)
            for i in range(n):
                if i == n - 1 : pre[i].next = None
                else : pre[i].next=pre[i+1]
                node=pre[i]
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)

            pre = q[:]
            q=[]

有没有其他的方法呢?

我们先来看看116题，对于满二叉树，我们每次遍历一层的时候,将左儿子的next设置为右儿子，将右儿子设置为兄弟节点的左儿子。

C++

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root) return;
        while(root->left){
            TreeLinkNode *cur = root, *p = nullptr;
            while(cur){
                cur->left->next = cur->right;
                p = cur->next;
                if(!p) break;
                cur->right->next = p->left;
                cur = p;
            }
            root = root->left;
        }
    }
};

Python

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        while root:
            t = root
            while t:
                if t.left:
                    t.left.next = t.right
                if t.right and t.next:
                    t.right.next = t.next.left
                t = t.next
            root = root.left

那么117题并不是满二叉树，这就需要另外一个指针，指向每一层的最左边的节点，然后父节点不断的遍历其兄弟节点，而该节点对next赋值并不断的移动到刚赋值的next节点即可。

C++

class Solution {
public:
    void connect(TreeLinkNode *root) {
        while(root){
            TreeLinkNode *cur = root, *first = nullptr, *p = first;
            while(cur){
                if(cur->left){
                    if(!p)
                        first = p = cur->left;
                    else
                        p = p->next = cur->left;
                }
                if(cur->right){
                    if(!p)
                        first = p = cur->right;
                    else
                        p = p->next = cur->right;
                }
                cur = cur->next;
            }
            root = first;
        }
    }
};

Python

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        while root:
            t, head = root, root.left if root.left else root.right
            while not head:
                t = root = root.next
                if not root: return
                head = root.left if root.left else root.right

            while t:
                if t.left and head != t.left:
                    head.next = head = t.left #head.next = t.left #head = head.next
                if t.right and head != t.right:
                    head.next = head = t.right
                t = t.next
            root = root.left if root.left else root.right

可用如下代码检验此题

def printTreeByLeavesNext(root):
    print [root.val]
    while root:
        L = root.left if root.left else root.right
        while not L:
            root = root.next
            if not root: return
            L = root.left if root.left else root.right
        line = []
        while L:
            line.append(L.val)
            L = L.next
        print line
        root = root.left

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,
1
2
3
  1
 / \
2   3
Return 6.

题目地址：leetcode Binary Tree Maximum Path Sum

题意：给定一棵二叉树，要求返回其路径中和最大值。（可以从任意起点开始到任意起点结束）

思路：DFS,设dfs(root)返回的是包括root这个结点的单一路径上的最大值。设L=dfs(root.left) ,R=dfs(root.right)如题目样例中的{1,2,3,}就是L=2,R=3

则可能的结果有：

L+R+root.val (左右子树和根构成路径为最大值，就是题目的情况）
max(L,R) + root.val(左或者右子树和根构成最大值）
root.val本身为最大值

和全局变量ans比较更新即可。

需要注意的是dfs返回值，可能是

max(L,R) + root.val 某一条路径
root.val 只是该结点（下面都是负的了）

Python

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        if not root:return 0
        self.INF,self.ans=-0x7ffffff,-0x7ffffff       
        self.dfs(root)
        return self.ans

    def dfs(self,root):
        if not root:return self.INF
        L , R = self.dfs(root.left) ,self.dfs(root.right)    
        if L + R + root.val > self.ans: self.ans=  L + R + root.val
        if max(L,R) + root.val> self.ans: self.ans= max(L,R)+ root.val     
        if root.val > self.ans: self.ans=root.val     
        return max(max(L,R) + root.val,root.val)

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,
1
2
3
4
  1
 / \
2   3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题目地址：leetcode 129 Sum Root to Leaf Numbers

题意：给定一棵仅由数字0~9组成的二叉树，求根到叶子结点各个路径数字组成的字符串之和

思路：继续DFS

Python

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = [0]
        self.dfs(root, 0, ans)
        return ans[0]
    
    def dfs(self, root, cur, ans):
        if not root: return
        if not root.left and not root.right:
            ans[0] += cur * 10 + root.val
        else:
            if root.left:
                self.dfs(root.left, cur * 10 + root.val, ans)
            if root.right:
                self.dfs(root.right, cur * 10 + root.val, ans)

C++

class Solution {
    void dfs(TreeNode *root, int cur, int &ans){
        if(!root) return;
        if(!root->left && !root->right){
            ans += cur * 10 + root->val;
            return;
        }
        if(root->left)
            dfs(root->left, cur * 10 + root->val, ans);
        if(root->right)
            dfs(root->right, cur * 10 + root->val, ans);
    }
    
public:
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        dfs(root, 0, ans);
        return ans;
    }
};

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},
1
2
3
4
5
6
1
 \
  2
 /
3
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

题目地址：leetcode Binary Tree Preorder Traversal

题意：给定二叉树，返回其前序遍历

思路：

直接递归。没难度。
用栈，记得应先右子树入栈。（why?递归的时候是先左子树的，而栈后进先出，故左子树要放后面入栈）

递归版

C++

class Solution {
    void dfs(TreeNode *root, vector<int> &ans){
        if(!root) return;
        ans.push_back(root->val);
        dfs(root->left, ans);
        dfs(root->right, ans);
    }
    
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
};

Python

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        ans = []
        self.dfs(root,ans)
        return ans
        
    def dfs(self,root,ans):
        if not root: return
        ans.append(root.val)
        self.dfs(root.left,ans)
        self.dfs(root.right,ans)

迭代版

C++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *cur = q.top();
            q.pop();
            ans.push_back(cur->val);
            if(cur->right) q.push(cur->right);
            if(cur->left) q.push(cur->left);
        }
        return ans;
    }
};

Python

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        if not root: return []
        ans, q = [],[]
        q.append(root)
        while q:
            cur=q.pop()
            if cur.right: q.append(cur.right)
            if cur.left: q.append(cur.left)
            ans.append(cur.val)
        return ans

145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

For example: Given binary tree {1,#,2,3},
1
2
3
4
5
6
1
 \
  2
 /
3
return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

题目地址：leetcode Binary Tree Postorder Traversal

题意：给定二叉树，返回其后序遍历

思路：递归就不说了。说说非递归版本。

我们做过，从前序和中序遍历构造出树，也做过从后序和中序遍历构造树的（见105和106题）

做完前序和中序的那时候我就想，前序和后序能否直接倒序得到？（想偷懒）

答案是否定的，我们来看看前序遍历：根-左子树-右子树

后序遍历：左子树-右子树-根把前序遍历倒过来：右子树-左子树-根！左右子树相反，不能直接倒！

但是这题，哼哼哼，先左子树入栈，在右子树入栈！(和前序遍历相反，也就是颠倒了左右子树），最后输出颠倒一下即可！

非递归版本

C++

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *cur = q.top();
            q.pop();
            ans.push_back(cur->val);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Python

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def postorderTraversal(self, root):
        if not root: return []
        ans,q=[],[]
        q.append(root)
        while q:
            cur=q.pop()          
            if cur.left: q.append(cur.left)
            if cur.right: q.append(cur.right)
            ans.append(cur.val)
        return ans[::-1]

递归版本

class Solution {
    void dfs(TreeNode *root, vector<int> &ans){
        if(!root) return;
        dfs(root->left, ans);
        dfs(root->right, ans);
        ans.push_back(root->val);
    }
    
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
};

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

leetcode 173 Binary Search Tree Iterator

题目：写一个二叉搜索树（BST），要求实现hasnext和next函数。调用时会这么调用：while i.hasNext(): v.append(i.next())

思路:我们知道中序遍历结果就是有序的序列。只要用非递归的实现中序遍历即可。（见94题）

Python

class BSTIterator:
    # @param root, a binary search tree's root node
    def __init__(self, root):
        self.q=[]
        self.allLeftIntoStack(root)

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        if not self.q:return False
        return True

    # @return an integer, the next smallest number
    def next(self):
        cur = self.q.pop()
        self.allLeftIntoStack(cur.right)
        return cur.val

    def allLeftIntoStack(self,root):
        while root:
            self.q.append(root)
            root=root.left

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,
1
2
3
4
5
   1            ---1
 /   \
2     3         ---3
 \     \
  5     4       ---4
You should return [1, 3, 4].

题目地址：leetcode 199 Binary Tree Right Side View

题目：给定一颗二叉树，求每一层最右边的结点。

思路: 两种方法，我用的是DFS

BFS，直接求得每一层最右边的，很好理解，我就不想写了。
DFS：先求深度，然后dfs，每次将找到的放在相应的层上。由于右面放的一定是右边的结点，所以能保证正确。

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def rightSideView(self, root):
        ans=[0] * self.depth(0,root)
        self.dfs(0,root,ans)
        return ans
    
    def depth(self,cur,root):
        if not root:return cur
        return max(self.depth(cur+1,root.left),self.depth(cur+1,root.right))

    def dfs(self,cur,root,ans):
        if not root:return 
        ans[cur]=root.val
        self.dfs(cur+1,root.left,ans)
        self.dfs(cur+1,root.right,ans)

222. Count Complete Tree Nodes

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

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

题目地址：leetcode 222 Count Complete Tree Nodes

题意：给定一个完全二叉树（它的所有非叶子结点都有左和右子结点），求它的结点数

思路: 直接深搜O(n) TLE了。所以采用别的方法。

对于一个结点，计算其左子树和右子树的高度。如果相等，那么为满二叉树，结点数为2^h -1 否则递归计算

int countNodes(struct TreeNode* root) {
    if(!root) return 0;
    int depth_left =0, depth_right =0;
    for(struct TreeNode* left = root;left;left=left->left) depth_left++;
    for(struct TreeNode* right = root;right;right=right->right) depth_right++;
    if(depth_left == depth_right) return (1<<depth_left) -1;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

Python

class Solution:
    # @param {TreeNode} root
    # @return {integer}
    def countNodes(self, root):
        if not root : return 0
        depth_left = depth_right = 0
        left = right = root 
        while left  : left ,  depth_left = left.left,depth_left+1
        while right : right , depth_right = right.right,depth_right+1
        if depth_left == depth_right : return (1<<depth_left)-1
        return  self.countNodes(root.left) + self.countNodes(root.right) + 1

226. Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1

题目地址：leetcode 226 Invert Binary Tree

题意：给定一个二叉树，让你把它倒过来

思路：DFS的时候交换左右结点即可

class Solution:
    # @param {TreeNode} root
    # @return {TreeNode}
    def invertTree(self, root):
        def dfs(root):
            if not root : return
            dfs(root.left)
            dfs(root.right)
            t = root.left
            root.left = root.right 
            root.right = t
        dfs(root)
        return root

C++

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

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

题目地址：leetcode 230 Kth Smallest Element in a BST

题意：给定BST，求BST中第k小的元素

思路: BST中序遍历为有序，所以直接中序遍历即可。

class Solution:
    # @param {TreeNode} root
    # @param {integer} k
    # @return {integer}
    def kthSmallest(self, root, k):
        ans = []
        def dfs(root):
            if not root :  return;
            dfs(root.left)
            ans.append(root.val)
            if len(ans) == k: return;
            dfs(root.right)
        dfs(root)
        return ans[k-1]

235. Lowest Common Ancestor of a Binary Search Tree

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
1
2
3
4
5
6
7
8
     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

题目地址：Lowest 235 Common Ancestor of a Binary Search Tree

题意：给定一颗二叉搜索树，求最近公共祖先(LCA)

思路：

LCA问题可以见我博客二叉树最近公共祖先详解（LCA问题详解）

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:return root;
        if p.val > q.val:return self.lowestCommonAncestor(root, q, p)
        if root.val >= p.val and root.val <= q.val: return root;
        if root.val < p.val:return self.lowestCommonAncestor(root.right, p, q)
        if root.val > q.val:return self.lowestCommonAncestor(root.left, p, q)

236. Lowest Common Ancestor of a Binary Tree

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
1
2
3
4
5
6
7
8
     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

题目地址：leetcode 236 Lowest Common Ancestor of a Binary Tree

题意：给定一颗二叉树，求最近公共祖先(LCA)

思路：

LCA问题可以见我博客二叉树最近公共祖先详解（LCA问题详解）

Python

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:
1
2
3
4
5
6
   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:
1
["1->2->5", "1->3"]

题目地址：leetcode Binary Tree Paths

题意：给定一棵二叉树，求它所有从根节点到叶子结点的路径。

思路：DFS。。。。。

class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        if not root: return []
        ans = []
        self.dfs(root, ans, str(root.val))
        return ans

    def dfs(self, root, ans, cur):
        if root.left:
            self.dfs(root.left, ans, cur + "->" + str(root.left.val))
        if root.right:
            self.dfs(root.right, ans, cur + "->" + str(root.right.val))

        if not root.left and not root.right:
            ans.append(cur)

297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree
1
2
3
4
5
  1
 / \
2   3
   / \
  4   5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

题目地址：leetcode 297 Serialize and Deserialize Binary Tree

题意：给定根节点，将树进行序列化为字符串，然后反序列化回来。

思路:

方法一：

采用和leetcode的序列化方法一样的。

BFS：

对于序列化，只需要首先将根放入队列，然后每次从队列取第一个cur。如果cur为空，输出"null,"，否则输出cur->val + ","。这里我用都好分隔符
对于反序列化，按分隔符","分割，每次取出。如果当前字符串t不为"null",则创建一个值为t的TreeNode，把当前结点的left或者right指向它。详见代码。

C++

class Codec {
public:
	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (!root) return "";
		string res;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			TreeNode *cur = q.front(); q.pop();
			if (!cur)
				res.append("null,");
			else {
				res.append(to_string(cur->val) + ",");
				q.push(cur->left);
				q.push(cur->right);
			}
		}
		return res.substr(0, res.size() - 1);
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		if (data.empty()) return nullptr;
		queue<TreeNode*> q;
		TreeNode *root = nullptr, *cur = nullptr;
		bool isLeft = true;
		for (string::iterator s = data.begin(), e; s != data.end(); s = e != data.end() ? next(e) : data.end()) {
			e = find(s, data.end(), ',');
			string sub = string(s, e);
			TreeNode *t = nullptr;
			if (sub != "null") {
				t = new TreeNode(stoi(sub));
				q.push(t);
			}
			if (root == nullptr) {
				root = cur = t;
				if (q.empty()) return root;
				q.pop();
			}
			else {
				if (isLeft)
					cur->left = t;
				else {
					cur->right = t;
					if (q.empty()) return root;
					cur = q.front(); q.pop();
				}
				isLeft = !isLeft;
			}
		}
		return root;
	}
};

Java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        LinkedList<TreeNode> q = new LinkedList<>();
        q.add(root);
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            TreeNode cur = q.pollFirst();
            if (cur != null) {
                q.add(cur.left);
                q.add(cur.right);
                res.append(cur.val);
            } else
                res.append("null");
            res.append(',');
        }
        res.deleteCharAt(res.length()-1);
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        LinkedList<TreeNode> q = new LinkedList<>();
        TreeNode root = null, cur = null;
        boolean isLeft = true;
        for (String s : data.split(",")) {
            TreeNode t = null;
            if (!s.equals("null")) {
                t = new TreeNode(Integer.parseInt(s));
                q.add(t);
            }
            if (root == null) {
                cur = root = q.pollFirst();
            } else {
                if (isLeft)
                    cur.left = t;
                else {
                    cur.right = t;
                    cur = q.pollFirst();
                }
                isLeft = !isLeft;
            }
        }
        return root;
    }
}

Python

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root: return ""
        q = collections.deque([root])
        res = []
        while q:
            cur = q.popleft()
            if cur:
                res.append(str(cur.val))
                q.append(cur.left)
                q.append(cur.right)
            else:
                res.append("null")
        return ",".join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data: return None
        q = collections.deque()
        root = cur = None
        is_left = True
        for s in data.split(","):
            t = None
            if s != "null":
                t = TreeNode(int(s))
                q.append(t)
            if root:
                if is_left:
                    cur.left = t
                else:
                    cur.right = t
                    if not q: return root
                    cur = q.popleft()
                is_left = not is_left
            else:
                if not q: return root
                root = cur = q.popleft()
        return root

另一种写法：反序列化的时候用i来维护子节点，队列来维护当前节点。

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return "[]"
        ans = []
        q = deque([root])
        while q:
            cur = q[0]
            q.popleft()
            if cur:
                q.append(cur.left)
                q.append(cur.right)
                ans.append(str(cur.val))
            else:
                ans.append("null")
        return '[{}]'.format(','.join(ans))

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '[]': return None
        data = data[1:-1].split(',')
        root = TreeNode(int(data[0]))
        i = 1
        q = deque([root])
        while q:
            cur = q.popleft()
            if i >= len(data):
                break
            
            if data[i] != 'null':
                cur.left = TreeNode(int(data[i]))
                q.append(cur.left)
            i += 1
            if data[i] != 'null':
                cur.right = TreeNode(int(data[i]))
                q.append(cur.right)
            i += 1
        return root

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

方法二

按前序遍历的方式建树

Java

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            TreeNode cur = q.pollLast();
            if (cur != null) {
                q.add(cur.right);
                q.add(cur.left);
                res.append(cur.val);
            } else
                res.append("null");
            res.append(',');
        }
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }

    private TreeNode deserializeHelper(final Deque<String> q) {
        if (q.isEmpty() ) return null;
        String s = q.pollFirst();
        if(s.equals("null")) return null;
        TreeNode cur = new TreeNode(Integer.parseInt(s));
        cur.left = deserializeHelper(q);
        cur.right = deserializeHelper(q);
        return cur;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        Deque<String> q= new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper( q);
    }
}

449. Serialize and Deserialize BST

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

题目地址：leetcode Serialize and Deserialize BST

题目大意：给定一棵BST，要求进行序列化和反序列化。要求序列化后的字符串尽可能的短。

思路：

和297. Serialize and Deserialize Binary Tree题的区别在于，这题是BST。

BST和其他的有啥用呢？在297题中，我们用null表示节点为空。但是这题不需要。我们可以根据节点的大小来判断应该在左子树还是右子树。

其实就是说BST可以直接用前序遍历恢复。而二叉树需要至少两种遍历的存储才行，不然就要加入额外的信息，如297用的null。

C++

class Codec {
public:
	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (!root) return "";
		string res;
		stack<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			TreeNode *cur = q.top(); q.pop();
			if (cur) {
				q.push(cur->right);
				q.push(cur->left);
				res.append(to_string(cur->val) + ",");
			}
		}
		return res.substr(0, res.size() - 1);
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		if (data.empty()) return nullptr;
		queue<int> q;
		for (auto s = data.begin(), e = s; s != data.end(); s = (e != data.end() ? next(e) : data.end())) {
			e = find(s, data.end(), ',');
			q.push(stoi(string(s, e)));
		}
		return buildTree(0x7fffffff, q);;
	}
    
private:
	TreeNode* buildTree(int maxV, queue<int> &q) {
		if (q.empty()) return nullptr;
		TreeNode* root = new TreeNode(q.front());
		q.pop();
		if (!q.empty() && q.front() < root->val)
			root->left = buildTree(root->val, q);
		if (!q.empty() && root->val < q.front() && q.front() < maxV)
			root->right = buildTree(maxV, q);
		return root;
	}
};

Java

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            TreeNode cur = q.pollLast();
            if (cur != null) {
                q.add(cur.right);
                q.add(cur.left);
                res.append(cur.val).append(',');
            }
        }
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }

    private TreeNode deserializeHelper(int max, final Deque<Integer> q) {
        if (q.isEmpty()) return null;
        TreeNode root = new TreeNode(q.pollFirst());
        if (!q.isEmpty() && q.peekFirst() < root.val)
            root.left = deserializeHelper(root.val, q);
        if (!q.isEmpty() && q.peekFirst() > root.val && max > q.peekFirst())
            root.right = deserializeHelper(max, q);
        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        Deque<Integer> q = new LinkedList<>();
        for (String s : data.split(","))
            q.add(Integer.parseInt(s));
        return deserializeHelper(Integer.MAX_VALUE, q);
    }
}

Python

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root: return ""
        q = collections.deque([root])
        res = []
        while q:
            cur = q.pop()
            if cur:
                q.append(cur.right)
                q.append(cur.left)
                res.append(str(cur.val))
        return ",".join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        def build_tree(max_v, q):
            if not q: return None
            root = TreeNode(q.popleft())
            if q and root.val > q[0]:
                root.left = build_tree(root.val, q)
            if q and root.val < q[0] < max_v:
                root.right = build_tree(max_v, q)
            return root

        return build_tree(0x7fffffff, q=collections.deque(map(int, data.split(",")))) if data else None

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/