94、二叉树的中序遍历

# 94、二叉树的中序遍历

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

示例:

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

输出: [1,3,2] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

# 前序中序后序遍历时有个模板

while( 栈非空 || p 非空)
{
    if( p 非空)
    {

    }
	else
    {

    }
}

1
2
3
4
5
6
7
8
9
10
11

# 1、自己写的方法，递归写法

其实就是左中右的递归写法

执行用时 :4 ms, 在所有 C++ 提交中击败了49.16%的用户

内存消耗 :8.3 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<int> inorderTraversal(TreeNode* root) {
	vector<int> result;
	if (root == nullptr) return result;
	return inorderTraversalCore(result, root);

}
vector<int> inorderTraversalCore(vector<int>& result, TreeNode* root) {
	if (root->left != nullptr)
		inorderTraversalCore(result, root->left);
	result.push_back(root->val);
	if (root->right != nullptr)
		inorderTraversalCore(result, root->right);
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2、根据栈的模板写的一种方法

vector<int> inorderTraversal(TreeNode* root) {
	stack<TreeNode*> s;
	vector<int> result;
	while (root != nullptr || !s.empty()) {
		if (root != nullptr) {
			s.push(root);
			root = root->left;
		}
		else {
			root = s.top();
			s.pop();
			result.push_back(root->val);
			root = root->right;
		}
	}
	return result;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 144. 二叉树的前序遍历 (opens new window)

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

示例:

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

输出: [1,2,3]

1
2
3
4
5
6
7
8

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

# 前序中序后序遍历时有个模板

while( 栈非空 || p 非空)
{
    if( p 非空)
    {

    }
	else
    {

    }
}

1
2
3
4
5
6
7
8
9
10
11

# 1、自己写的，递归写法

执行用时 :4 ms, 在所有 C++ 提交中击败了51.68%的用户

内存消耗 :9.9 MB, 在所有 C++ 提交中击败了16.28%的用户

vector<int> preorderTraversal(TreeNode* root) {
	vector<int> result;
	if (root == nullptr) return result;
	return preorderTraversalCore(result, root);

}
vector<int> preorderTraversalCore(vector<int>& result, TreeNode* root) {
	if(root!=nullptr)
		result.push_back(root->val);
	if (root->left != nullptr)
		preorderTraversalCore(result, root->left);
	if (root->right != nullptr)
		preorderTraversalCore(result, root->right);
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 2、模板写法，这个模板很厉害

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<int> preorderTraversal(TreeNode* root) {
	stack<TreeNode*> s;
	vector<int> result;
	while (root != nullptr || !s.empty()) {
		if (root != nullptr) {
			result.push_back(root->val);
			s.push(root);
			root = root->left;
		}
		else {
			root = s.top();
			s.pop();
			root = root->right;
		}
	}
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 二刷迭代与递归

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：8.5 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<int> preorderTraversal(TreeNode* root) {
	if (root == nullptr) return vector<int>();
	stack<TreeNode*> s;
	vector<int> result;
	while (!s.empty() || root != nullptr) {
		if (root != nullptr) {
			result.push_back(root->val);
			s.push(root);
			root = root->left;
		
		}
		else {
			root = s.top();
			s.pop();
			root = root->right;
		}
	}
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

执行用时：4 ms, 在所有 C++ 提交中击败了50.37%的用户

内存消耗：8.5 MB, 在所有 C++ 提交中击败了100.00%的用户

void preorderTraversalCore(TreeNode* node, vector<int>& result) {
	if (node == nullptr) return;
	result.push_back(node->val);
	if(node->left) preorderTraversalCore(node->left, result);
	if (node->right) preorderTraversalCore(node->right, result);
}

vector<int> preorderTraversal(TreeNode* root) {
	if (root == nullptr) return vector<int>();
	vector<int> result;
	preorderTraversalCore(root, result);
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 145. 二叉树的后序遍历 (opens new window)

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

示例:

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

输出: [3,2,1]

1
2
3
4
5
6
7
8

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

# 前序中序后序遍历时有个模板

while( 栈非空 || p 非空)
{
    if( p 非空)
    {

    }
	else
    {

    }
}

1
2
3
4
5
6
7
8
9
10
11

# 1、一种巧妙的写法，真的很妙

递归先序，根右左的顺序，然后反转容器

执行用时 :4 ms, 在所有 C++ 提交中击败了52.20%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> result;
	if (root == nullptr) return result;
	postorderTraversalCore(result, root);
	reverse(result.begin(), result.end());//千万别忘了反转，后序本来是左右根，现在是根右左，所以要反转一下
	return result;

}
void postorderTraversalCore(vector<int>& result, TreeNode* root) {//根右左，最后再反转一下即可
	if (root != nullptr)
		result.push_back(root->val);
	if (root->right != nullptr)
		postorderTraversalCore(result, root->right);
	if (root->left != nullptr)
		postorderTraversalCore(result, root->left);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 2、也可以直接左右根的形式来做递归，这样就不用反转了

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.4 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> result;
	if (root == nullptr) return result;
	postorderTraversalCore(result, root);
	return result;

}
void postorderTraversalCore(vector<int>& result, TreeNode* root) {
	if (root->left != nullptr)
		postorderTraversalCore(result, root->left);
	if (root->right != nullptr)
		postorderTraversalCore(result, root->right);
	result.push_back(root->val);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 3、模板的迭代写法

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<int> postorderTraversal(TreeNode* root) {
	stack<TreeNode*> s;
	vector<int> result;//按照左右根的反转根右左的顺序保存进result中，最后再翻转一下
	while (root != nullptr || !s.empty()) {
		if (root != nullptr) {
			result.push_back(root->val);
			s.push(root);
			root = root->right;
		}
		else {
			root = s.top();
			s.pop();
			root = root->left;
		}
	}
	reverse(result.begin(), result.end());
	return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 面试题07. 重建二叉树 (opens new window)

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

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

1
2

返回如下的二叉树：

1
2
3
4
5

限制：

0 <= 节点个数 <= 5000

# 1、很经典的建树问题，看的解析，很厉害

执行用时 :20 ms, 在所有 C++ 提交中击败了92.50%的用户

内存消耗 :25.8 MB, 在所有 C++ 提交中击败了100.00%的用户

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

	unordered_map<int, int> unmp;
	for (int i = 0; i < preorder.size(); ++i) {
		unmp.insert({ inorder[i],i });
	}
	return build(preorder, unmp, 0, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, unordered_map<int, int>& unmp, int pre_root, int in_start, int in_end) {//前序的root  中序的start和end
	if (in_start > in_end) return NULL;
	TreeNode* tree = new TreeNode(preorder[pre_root]);
	int in_root_index = unmp[preorder[pre_root]];

	tree->left = build(preorder, unmp, pre_root + 1, in_start, in_root_index - 1);
	tree->right = build(preorder, unmp, (pre_root + 1) + (in_root_index - 1 - in_start) + 1, in_root_index + 1, in_end);//左子树的根的位置，加上左子树的长度就等于前序中右子树根的索引
	return tree;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 2、一种更容易懂的递归方法

速度稍差一点，但是从理解上来说更容易懂一点

执行用时 :76 ms, 在所有 C++ 提交中击败了25.46%的用户

内存消耗 :74.3 MB, 在所有 C++ 提交中击败了100.00%的用户

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {	
	if (preorder.size() == 0 || inorder.size() == 0) {
		return nullptr;
	}
	TreeNode* treeNode = new TreeNode(preorder[0]);
	int mid = distance(begin(inorder), find(inorder.begin(), inorder.end(), preorder[0]));
	vector<int> left_pre(preorder.begin() + 1, preorder.begin() + mid + 1);
	vector<int> right_pre(preorder.begin() + mid + 1, preorder.end());
	vector<int> left_in(inorder.begin(), inorder.begin() + mid);
	vector<int> right_in(inorder.begin() + mid + 1, inorder.end());

	treeNode->left = buildTree(left_pre, left_in);
	treeNode->right = buildTree(right_pre, right_in);
	return treeNode;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 面试题33. 二叉搜索树的后序遍历序列 (opens new window)

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

1
2
3
4
5

示例 1：

输入: [1,6,3,2,5]
输出: false

1
2

示例 2：

输入: [1,3,2,6,5]
输出: true

1
2

提示：

数组长度 <= 1000

# 1、递归写法

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :6.9 MB, 在所有 C++ 提交中击败了100.00%的用户

bool verifyPostorder(vector<int>& postorder) {
	if (postorder.empty())  return true; //不太对，输入为空，应该返回false的
	return verifyPostorderCore(postorder, 0, postorder.size() - 1);
}

bool verifyPostorderCore(vector<int>& postorder, int start, int end) {
	if (start >= end)return true;
	int left = start;
	while (left < end && postorder[left] < postorder[end])  ++left;

	for (int i = left; i < end; ++i) {
		if (postorder[i] <= postorder[end]) return false;
	}
	return verifyPostorderCore(postorder, start, left-1) &&
		verifyPostorderCore(postorder, left, end-1);;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 面试题34. 二叉树中和为某一值的路径 (opens new window)

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

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

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

1
2
3
4
5
6
7

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

1
2
3
4

提示：

节点总数 <= 10000

# 1、递归做法，有点回溯的意思

执行用时 :12 ms, 在所有 C++ 提交中击败了85.48%的用户

内存消耗 :20.2 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
vector<vector<int>> result;
vector<int> path;
public:
    void  pathSumCore(TreeNode*root,int sum){
        if(root==nullptr) return;
        path.push_back(root->val);
        if(root->left==nullptr && root->right==nullptr && sum == root->val)
            result.push_back(path);
        else{

            if(root->left!=nullptr)   pathSumCore(root->left,sum-root->val);
            if(root->right!=nullptr)   pathSumCore(root->right,sum-root->val);
        }
        path.pop_back();

    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {

        if(root==nullptr) return result;
        pathSumCore(root,sum);
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 面试题26. 树的子结构 (opens new window)

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

3 / \ 4 5 / \ 1 2 给定的树 B：

4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

1
2

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

1
2

限制：

0 <= 节点个数 <= 10000

# 1、改了许久的一种写法

执行用时 :72 ms, 在所有 C++ 提交中击败了61.82%的用户

内存消耗 :33.6 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
public:
bool HasSubtreeCore(TreeNode* pRoot1, TreeNode* pRoot2) {
	if (pRoot1 == nullptr && pRoot2 == nullptr)  return true;
	if (pRoot1 == nullptr && pRoot2 != nullptr) return false;
	if (pRoot1 != nullptr && pRoot2 == nullptr) return true;
	if (pRoot1->val == pRoot2->val)
		return HasSubtreeCore(pRoot1->left, pRoot2->left) && HasSubtreeCore(pRoot1->right, pRoot2->right); // 这里必须是 与
	else
		return false;
}
bool isSubStructure(TreeNode* A, TreeNode* B)
{
	if (A == nullptr || B == nullptr) return false;
	return isSubStructure(A->left, B) || isSubStructure(A->right, B) || HasSubtreeCore(A,B);//注意这里的写法是 或
}

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

稍微优化一点点

执行用时 :64 ms, 在所有 C++ 提交中击败了81.74%的用户

内存消耗 :33.6 MB, 在所有 C++ 提交中击败了100.00%的用户

bool HasSubtreeCore(TreeNode* pRoot1, TreeNode* pRoot2) {
	if (pRoot2 == nullptr)  return true;// p2为空，不管p1是不是空都是正确的
	if (pRoot1 == nullptr) return false;// p1为空，p2不为空，一定是错误的
    
	if (pRoot1->val == pRoot2->val)
		return HasSubtreeCore(pRoot1->left, pRoot2->left) && HasSubtreeCore(pRoot1->right, pRoot2->right);// 这里必须是 与
	else
		return false;
}
bool isSubStructure(TreeNode* A, TreeNode* B)
{
	if (A == nullptr || B == nullptr) return false;
	return isSubStructure(A->left, B) || isSubStructure(A->right, B) || HasSubtreeCore(A,B);//注意这里的写法是 或
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 2、以下这种写法是不对的，真的要小心

bool HasSubtreeCore(TreeNode* pRoot1, TreeNode* pRoot2) {
	if ( pRoot2 == nullptr)  return true;
	if (pRoot1 == nullptr) return false;
	if (pRoot1->val == pRoot2->val)
		return HasSubtreeCore(pRoot1->left, pRoot2->left) && HasSubtreeCore(pRoot1->right, pRoot2->right);
	else
		return false;
}
bool isSubStructure(TreeNode* A, TreeNode* B)
{
	if (A == nullptr || B == nullptr) return false;
	//先判断p2是否在p1中
	if (A->val == B->val)  return HasSubtreeCore(A->left, B->left) && HasSubtreeCore(A->right, B->right); //不可以在这里直接判断其左右子树，因为有时候树中有可能有重复的数字
	return isSubStructure(A->left, B) || isSubStructure(A->right, B);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[4,2,3,4,5,6,7,8,9] [4,8,9]

这种输入的话，会直接走到 if (A->val == B->val) 这一步，不会走到 isSubStructure(A->left, B) || isSubStructure(A->right, B) 这一步，因此不能这么写

# 面试题32 - I. 从上到下打印二叉树 (opens new window)

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

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

1
2
3
4
5

[3,9,20,15,7]

提示：

节点总数 <= 1000

# 1、挺容易的，相当于层次遍历吧

执行用时：4 ms, 在所有 C++ 提交中击败了87.16%的用户

内存消耗：12.5 MB, 在所有 C++ 提交中击败了100.00%的用户

    vector<int> levelOrder(TreeNode* root) {
        vector<int> result;
        if(root==nullptr) return result;
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* node;
        while(!q.empty()){

            node = q.front();
            q.pop();
            result.push_back(node->val);
            if(node->left)  q.push(node->left);
            if(node->right)  q.push(node->right);
        }
        return result;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 面试题32 - II. 从上到下打印二叉树 II (opens new window)

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

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

1
2
3
4
5

返回其层次遍历结果：

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

1
2
3
4
5

提示：

节点总数 <= 1000

# 1、两个栈，层次遍历即可

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：12.7 MB, 在所有 C++ 提交中击败了100.00%的用户

    vector<vector<int>> levelOrder(TreeNode* root) {

        	vector<vector<int>> result;
	if (root == nullptr) return result;
	queue<TreeNode*> q1,q2;
	q1.push(root);
	TreeNode* node;
	vector<int> temp;
	while (!q1.empty() || !q2.empty()) {	
		temp.clear();
		while (!q1.empty()) {
			node = q1.front();
			q1.pop();
			temp.push_back(node->val);
			if (node->left)  q2.push(node->left);
			if (node->right)  q2.push(node->right);
		}
		if(temp.size())  result.push_back(temp);

		temp.clear();
		while (!q2.empty()) {
			node = q2.front();
			q2.pop();
			temp.push_back(node->val);
			if (node->left)  q1.push(node->left);
			if (node->right)  q1.push(node->right);
		}
		if (temp.size())  result.push_back(temp);
	}
	return result;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 2、改为一个栈也是可以的

执行用时：4 ms, 在所有 C++ 提交中击败了89.74%的用户

内存消耗：12.6 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<vector<int>> levelOrder(TreeNode* root) {

vector<vector<int>> result;
	if (root == nullptr) return result;
	queue<TreeNode*> q;
	q.push(root);
	TreeNode* node;

	while (!q.empty()) {	
		int count = q.size();
		vector<int> temp;
		while (count--) {
				node = q.front();
				q.pop();
				temp.push_back(node->val);
				if (node->left)  q.push(node->left);
				if (node->right)  q.push(node->right);
		}
		result.push_back(temp);
		
	}
	return result;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 面试题 32 - III. 从上到下打印二叉树 III (opens new window)

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

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

1
2
3
4
5

返回其层次遍历结果：

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

1
2
3
4
5

提示：

节点总数 <= 1000

# 1、剑指offer上的题目，两个栈来回导出

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：12.8 MB, 在所有 C++ 提交中击败了100.00%的用户

	vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> result;
		if (root == nullptr) return result;
		stack<TreeNode*> left_right, right_left;
		left_right.push(root);
		TreeNode* node;
		while (!left_right.empty() || !right_left.empty()) {
			vector<int> temp;
			while (!left_right.empty()) {
				node = left_right.top();
				left_right.pop();
				temp.push_back(node->val);
				if (node->left)  //注意这里是先左再右
				right_left.push(node->left);
				if (node->right)  right_left.push(node->right);
			}
			if (temp.size()) {
				result.push_back(temp);
				temp.clear();
			}

			while (!right_left.empty()) {
				node = right_left.top();
				right_left.pop();
				temp.push_back(node->val);
                if (node->right) //这里是先右再左
                    left_right.push(node->right);
				if (node->left)  left_right.push(node->left);
	
			}
			if (temp.size()) {
				result.push_back(temp);
			}

		}
        return result;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 2、一个栈也可以做

执行用时：8 ms, 在所有 C++ 提交中击败了56.60%的用户

内存消耗：12.9 MB, 在所有 C++ 提交中击败了100.00%的用户

vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> ans;
	if (root == nullptr) {
		return ans;
	}
	queue<TreeNode*> q;
	q.push(root);
	bool isLeft = false;
	while (!q.empty()) {
		int rowLen = q.size();
		vector<int> temp;
		for (int i = 0; i < rowLen; ++i) {
			TreeNode* curNode = q.front();
			q.pop();
			if (curNode != nullptr) {
				temp.push_back(curNode->val);
				if (curNode->left)q.push(curNode->left);
				if (curNode->right)q.push(curNode->right);
			}
		}
		isLeft = !isLeft;
		if (!isLeft) {
			ans.push_back(vector<int>(temp.rbegin(), temp.rend()));//注意这里是要翻转一下的，这样就做到了从右向左
		}
		else {
			ans.push_back(temp);
		}
	}
	return ans;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 230. 二叉搜索树中第K小的元素 (opens new window)

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

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

示例 1:

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

1
2
3
4
5
6
7

示例 2:

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

1
2
3
4
5
6
7
8
9

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

# 1、自己写的笨方法，先全部保存下来再进行排序，时间复杂度太大

执行用时：36 ms, 在所有 C++ 提交中击败了38.06%的用户

内存消耗：26.3 MB, 在所有 C++ 提交中击败了5.00%的用户

    int kthSmallest(TreeNode* root, int k) {
	map<int, TreeNode*> result;
	queue<TreeNode*> q;
	q.push(root);
	TreeNode* node;
	while (!q.empty()) {
		node = q.front();
		q.pop();
		result.insert({node->val,node});
		if (node->left)  q.push(node->left);
		if (node->right)  q.push(node->right);
	}
	map<int, TreeNode*>::const_iterator it;
	it = result.begin();
	while (--k) it++;
	return it->first;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 2、借助二叉树迭代遍历模板的一种写法

   int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> s;
	int num = 0;
	while (!s.empty() || root!=nullptr)
	{
		if (root !=nullptr)
		{
			s.push(root);
			root = root->left;
		}
		else
		{
			root = s.top();
			s.pop();
			num++;
			if (num == k)
				return root->val;
			root = root->right;
		}
	}
	return 0;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 3、二叉树递归遍历的一种写法

执行用时：32 ms, 在所有 C++ 提交中击败了59.00%的用户

内存消耗：24 MB, 在所有 C++ 提交中击败了5.00%的用户

void kthSmallestCore(TreeNode* root, int& k, int& ans) {
	if (root == nullptr) return;
	if (root->left) kthSmallestCore(root->left, k, ans);
	k--;
	if (k == 0) {
		ans = root->val;
	}
	if(root->right) kthSmallestCore(root->right, k, ans);

}

int kthSmallest(TreeNode* root, int k) {
	int ans = 0;
	kthSmallestCore(root, k, ans);
	return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 剑指 Offer 54. 二叉搜索树的第k大节点 (opens new window)

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

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

1
2
3
4
5
6
7

示例 2:

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

1
2
3
4
5
6
7
8
9

限制：

1 ≤ k ≤ 二叉搜索树元素个数

# 1、后序遍历递归写法

执行用时：32 ms, 在所有 C++ 提交中击败了62.54%的用户

内存消耗：24.3 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
public:

	int count=0,result = 0;
	void kthLargestCore(TreeNode* root, int k) {
		if (root == nullptr) return ;
		if (root->right) kthLargestCore(root->right, k);
		count++;
		if (count == k) { result = root->val; return; }
		if (root->left) kthLargestCore(root->left, k);
		return;
	}
	int kthLargest(TreeNode* root, int k) {
		
		kthLargestCore(root, k);		
		return result;;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 2、后序遍历递归写法，改进一点

class Solution {
public:
	int result = 0;
	void kthLargestCore(TreeNode* root, int &k) {
		if (root == nullptr) return ;
		if (root->right) kthLargestCore(root->right, k);
		k--;
		if (k == 0) { result = root->val; return; }
		if (root->left) kthLargestCore(root->left, k);
		return;
	}
	int kthLargest(TreeNode* root, int k) {
		
		kthLargestCore(root, k);		
		return result;;
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 3、后序遍历迭代模板写法，这种方法还是比较快

执行用时：28 ms, 在所有 C++ 提交中击败了80.90%的用户

内存消耗：24.1 MB, 在所有 C++ 提交中击败了100.00%的用户

 int kthLargest(TreeNode* root, int k) {

        if (root == nullptr) return 0;
		int count = 0;
		stack<TreeNode*>s;
		while (!s.empty() || root != nullptr) {

			if (root != nullptr) {
				s.push(root);
				root = root->right;
			}
			else {
				root = s.top();
				s.pop();
				k--;
				if (k == 0) return root->val;
				root = root->left;

			}
		}
		return 0;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 剑指 Offer 37. 序列化二叉树 (opens new window)

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

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

1
2
3
4
5
6
7
8
9

# 1、跟牛客上有一点不太一样

执行用时：88 ms, 在所有 C++ 提交中击败了30.97%的用户

内存消耗：39.7 MB, 在所有 C++ 提交中击败了100.00%的用户

class Codec {
private:
	TreeNode* deserializeCore(string& data, int &i) {
		if (data[i] == '#') {
			i++;
			return nullptr;
		}
		int num = 0, negativeFlag=1;
		if (data[i] == '-') {//序号考虑节点值为负数的情况
			negativeFlag = -1;
			i++;
		}
		while (data[i] != '!') {		
			num = num * 10 + data[i] - '0';
			i++;
		}
		num = num * negativeFlag;


		TreeNode* root = new TreeNode(num);
		root->left = deserializeCore(data, ++i);
		root->right = deserializeCore(data, ++i);
		return root;
	}

public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (root == nullptr) return "#!";
		string str = to_string(root->val) + '!';
		str += serialize(root->left);
		str += serialize(root->right);
		return str;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		int i = 0;
		return deserializeCore(data, i);
	}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 94、二叉树的中序遍历

# 前序中序后序遍历时有个模板

# 1、自己写的方法，递归写法

# 2、根据栈的模板写的一种方法

# 前序中序后序遍历时有个模板

# 1、自己写的，递归写法

# 2、模板写法，这个模板很厉害

# 二刷 迭代与递归

# 前序中序后序遍历时有个模板

# 1、一种巧妙的写法，真的很妙

# 2、也可以直接左右根的形式来做递归，这样就不用反转了

# 3、模板的迭代写法

# 1、很经典的建树问题，看的解析，很厉害

# 2、一种更容易懂的递归方法

# 1、递归写法

# 1、递归做法，有点回溯的意思

# 1、改了许久的一种写法

# 2、以下这种写法是不对的，真的要小心

# 1、挺容易的，相当于层次遍历吧

# 1、两个栈，层次遍历即可

# 2、改为一个栈也是可以的

# 1、剑指offer上的题目，两个栈来回导出

# 2、一个栈也可以做

# 1、自己写的笨方法，先全部保存下来再进行排序，时间复杂度太大

# 2、借助二叉树迭代遍历模板的一种写法

# 3、二叉树递归遍历的一种写法

# 1、后序遍历递归写法

# 2、后序遍历递归写法，改进一点

# 3、后序遍历迭代模板写法，这种方法还是比较快

# 1、跟牛客上有一点不太一样

# 二刷迭代与递归