Java代码实现在一棵二叉链表表示的二叉树中求一颗二叉树在后根次序遍历下第一个访问的结点
时间: 2024-03-10 10:50:33 浏览: 12
可以通过后序遍历的逆序来实现。具体做法如下:
1. 定义一个指针p指向二叉树的根节点,一个指针pre指向上次访问的节点;
2. 如果p的左右子树均为空或者上一次访问的节点是p的左右子树中的一个,则访问p节点,指向pre指针;
3. 如果p的左子树非空且上一次访问的节点不是p的左子树,则将p指向左子树;
4. 如果p的左子树为空且右子树非空且上一次访问的节点不是p的右子树,则将p指向右子树;
5. 如果p的左右子树均非空且上一次访问的节点不是p的左右子树,则将p指向左子树。
Java代码实现如下:
```
public TreeNode findLastVisitedNode(TreeNode root) {
if (root == null) {
return null;
}
TreeNode p = root;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.peek();
if (p.right == null || pre == p.right) {
stack.pop();
// 访问p节点
if (stack.isEmpty()) {
return p;
}
pre = p;
p = null;
} else {
p = p.right;
}
}
return null;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)