题意
判断一颗数是否是平衡二叉树。
平衡二叉树。左孩子节点,总是小于父节点,右孩子节点总是大于父节点。
对于每一个节点都符合这样的特性。
解法
不是很麻烦,对于平衡二叉树来说,它的中序遍历必定是一个升序序列。
直接中序遍历,如果出现后面的节点小于前面必定不是平衡二叉树
public boolean isValidBST(TreeNode root) {
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null){
while (root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
//加入结果
if (pre != null && pre.val >= root.val)
return false;
pre = root;
root = root.right ;
}
return true;
}
这里保存的是上一个节点,如果只保存上一个值,需要考虑int值上下界限。有可能输入Integer.MAX_VALUE的这种情况
网友评论