二叉树的创建与非递归遍历
时间: 2023-12-18 09:05:13 浏览: 30
二叉树的创建可以通过递归和非递归两种方式实现。其中,递归方式比较简单,非递归方式需要借助栈来实现。
1. 递归创建二叉树
递归创建二叉树的基本思路是:先创建根节点,再递归创建左子树和右子树。具体实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def create_tree(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = create_tree(nums[:mid])
root.right = create_tree(nums[mid+1:])
return root
```
2. 非递归创建二叉树
非递归创建二叉树的基本思路是:先创建根节点,再将根节点入栈,然后循环执行以下操作:从栈中取出一个节点,读入该节点的左右子节点,将左右子节点入栈。具体实现如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def create_tree(nums):
if not nums:
return None
root = TreeNode(nums[0])
stack = [root]
i = 1
while i < len(nums):
node = stack.pop(0)
if nums[i] is not None:
node.left = TreeNode(nums[i])
stack.append(node.left)
i += 1
if i < len(nums) and nums[i] is not None:
node.right = TreeNode(nums[i])
stack.append(node.right)
i += 1
return root
```
二叉树的非递归遍历需要借助栈来实现。具体实现如下:
1. 非递归前序遍历
前序遍历的基本思路是:先访问根节点,再访问左子树,最后访问右子树。具体实现如下:
```python
def preorder_traversal(root):
if not root:
return []
stack, res = [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
```
2. 非递归中序遍历
中序遍历的基本思路是:先访问左子树,再访问根节点,最后访问右子树。具体实现如下:
```python
def inorder_traversal(root):
if not root:
return []
stack, res = [], []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
```
3. 非递归后序遍历
后序遍历的基本思路是:先访问左子树,再访问右子树,最后访问根节点。具体实现如下:
```python
def postorder_traversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
```