美文网首页
算法:判断一棵树是否是平衡二叉树

算法:判断一棵树是否是平衡二叉树

作者: CharlesCT | 来源:发表于2021-03-19 22:29 被阅读0次

    题意

    判断一颗数是否是平衡二叉树。
    平衡二叉树。左孩子节点,总是小于父节点,右孩子节点总是大于父节点。
    对于每一个节点都符合这样的特性。

    解法

    不是很麻烦,对于平衡二叉树来说,它的中序遍历必定是一个升序序列。
    直接中序遍历,如果出现后面的节点小于前面必定不是平衡二叉树

      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的这种情况

    相关文章

      网友评论

          本文标题:算法:判断一棵树是否是平衡二叉树

          本文链接:https://www.haomeiwen.com/subject/vfmbcltx.html