admin 管理员组

文章数量: 887021

收藏

参考力扣题解
作者：hzhu212
链接：/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

此思路复杂度低，且简洁易懂，对于前序、中序、后序遍历，能够写出完全一致的代码，只需要调整左右节点的入栈顺序即可。
（注：由于栈FIFO的特性，入栈顺序应与遍历顺序相反，如中序遍历为左、中、右，则入栈顺序为右、中、左。）

核心思想如下：

  • 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
  • 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依 次入栈。
  • 如果遇到的节点为灰色，则将节点的值输出。
public class 二叉树的中序遍历_94 {class ColorNode {TreeNode node;String color;public ColorNode(TreeNode node, String color) {this.node = node;this.color = color;}}public List<Integer> inorderTraversal(TreeNode root) {if (root == null) {return new ArrayList<Integer>();}List<Integer> res = new ArrayList<>();Stack<ColorNode> stack = new Stack<>();stack.push(new ColorNode(root, "white"));while (!stack.empty()) {ColorNode cn = stack.pop();if (cn.color.equals("white")) {if (cn.node.right != null) {stack.push(new ColorNode(cn.node.right, "white"));}stack.push(new ColorNode(cn.node, "gray"));if (cn.node.left != null) {stack.push(new ColorNode(cn.node.left, "white"));}} else {res.add(cn.node.val);}}return res;}
}

本文标签： 收藏

版权声明：本文标题：收藏 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687383912h96442.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。