给定一个二叉树,输入: [1,null,2,3] 输出[1,2,3]
时间: 2023-11-22 10:55:15 浏览: 47
这是一道二叉树的遍历问题,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。
下面是一个使用DFS的递归解法:
```python
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
if not root:
return res
res += self.inorderTraversal(root.left)
res.append(root.val)
res += self.inorderTraversal(root.right)
return res
```
其中,inorderTraversal 函数接受一个 TreeNode 类型的参数 root,表示二叉树的根节点,返回一个 List[int] 类型的数组 res,表示遍历结果。
解法的思路是:
1. 如果二叉树为空,则返回一个空数组。
2. 否则,先遍历左子树,将遍历结果加入 res 中。
3. 将当前节点的值加入 res 中。
4. 最后遍历右子树,将遍历结果加入 res 中。
5. 返回 res。
运行该代码可以得到题目所求的输出。
相关问题
给定一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 输入样例1: 输入:2 1 3 输出:True 输入样例2: 输入:5 1 4 null null 3 6 输出:False C语言
很高兴能和您进行对话,我是ChitGPT,以下是回答您的问题:
要判断一个二叉树是否为二叉搜索树,需要满足两个条件:
1. 左子树的所有节点的值都小于根节点的值;
2. 右子树的所有节点的值都大于根节点的值。
同时,左右子树也必须也都是二叉搜索树。
基于以上条件,我们可以编写一个递归的算法来判断二叉树是否为二叉搜索树:
```
#include <limits.h>
bool isValidBST(struct TreeNode* root) {
return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}
bool isValidBSTHelper(struct TreeNode* root, long min_val, long max_val) {
if (root == NULL) {
return true;
}
if (root->val <= min_val || root->val >= max_val) {
return false;
}
return isValidBSTHelper(root->left, min_val, root->val) &&
isValidBSTHelper(root->right, root->val, max_val);
}
```
在这个算法中,isValidBSTHelper是一个递归函数,它判断以root为根节点的二叉树是否为二叉搜索树,min_val和max_val分别代表左右子树的值域范围。初始调用时,我们可以将min_val设为LONG_MIN,max_val设为LONG_MAX。然后,我们递归地检查左右子树是否也是二叉搜索树,只有当左右子树都是二叉搜索树,且根节点的值在min_val和max_val之间,才说明整棵树是二叉搜索树。
以上就是判断二叉树是否为二叉搜索树的算法,希望能够帮助到您。如果您还有其他问题,欢迎继续提问。
给定一个二叉树,返回它的 前序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]
好的,这是一道二叉树的经典问题。我们可以使用递归或者迭代的方式来实现前序遍历。
首先,我们来看递归方法的实现:
```python
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
res.append(root.val)
res += self.preorderTraversal(root.left)
res += self.preorderTraversal(root.right)
return res
```
其次,我们来看迭代方法的实现,使用栈来处理:
```python
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
以上两种方法都可以实现前序遍历,其中递归方法比较简单易懂,但是可能存在栈溢出的风险;迭代方法使用栈来实现,避免了栈溢出的问题,但是需要自己维护一个栈结构。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)