用前序遍历实现二叉树的search
时间: 2023-11-20 11:05:33 浏览: 31
二叉树的search操作实际上就是遍历二叉树查找目标节点,而前序遍历是一种遍历方式,可以用来实现search操作。具体的实现方法如下:
1. 从根节点开始遍历,将当前节点加入待访问栈中。
2. 如果当前节点为空或者栈为空,说明已经遍历完了整个二叉树,直接返回null。
3. 取出待访问栈中的栈顶节点,如果该节点是目标节点,则返回该节点。
4. 否则,将该节点的右子节点和左子节点(注意顺序)依次加入待访问栈中。
5. 回到步骤2,重复以上操作。
以下是一个示例代码实现:
```
public TreeNode search(TreeNode root, int target) {
if (root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.val == target) {
return node;
}
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return null;
}
```
其中TreeNode是二叉树节点的定义,包含左右子节点和节点值。注意,这里使用的是非递归的方式实现search操作,相较于递归方式,可以避免因递归深度过大而导致的栈溢出问题。