Morris遍历

2024-07-09 16:59| 来源: 网络整理| 查看: 265

题目链接：力扣

方法一：DFS

实现思路：递归算出每一个节点为头节点的树的最大值和最小值，以及它是否是二叉搜索树。根节点满足左子树的最大值小于自己、右子树的最大值大于自己，且左右子树都是二叉搜索树，返回true。直接看实现代码，重点说Morris遍历：

public boolean isValidBST(TreeNode root) { return method(root).isBSt; } public static class Info { private boolean isBSt; private int max; private int min; public Info(boolean isBSt, int max, int min) { this.isBSt = isBSt; this.max = max; this.min = min; } } public Info method(TreeNode node) { if (node == null) { return null; } Info leftInfo = method(node.left); Info rightInfo = method(node.right); int max = node.val; int min = node.val; if (leftInfo != null) { max = Math.max(leftInfo.max, max); } if (rightInfo != null) { max = Math.max(rightInfo.max, max); } if (leftInfo != null) { min = Math.min(leftInfo.min, min); } if (rightInfo != null) { min = Math.min(rightInfo.min, min); } boolean isBSt = true; if (leftInfo != null && !leftInfo.isBSt) { isBSt = false; } if (rightInfo != null && !rightInfo.isBSt) { isBSt = false; } if (leftInfo != null && leftInfo.max >= node.val) { isBSt = false; } if (rightInfo != null && rightInfo.min = list.get(i + 1)) { return false; } } return true; } public static List process(TreeNode node) { List list = new ArrayList(); if (node == null) { return list; } TreeNode cur = node; while (cur != null) { TreeNode mostRight = cur.left; if (mostRight != null) { while (mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if (mostRight.right == null) { mostRight.right = cur; cur = cur.left; } else { mostRight.right = null; list.add(cur.val);//第二次到cur才处理 cur = cur.right; } } else {//当前左子树为空，cur不会来第二次 list.add(cur.val); cur = cur.right; } } return list; }

【本文地址】

公司简介

联系我们