P4. 判断二叉树是否对称

https://algocasts.io/episodes/Q2preGz9

使用stack进行二叉树判断的部分

    stack.push(s.left);
    stack.push(t.right);
    stack.push(s.right);
    stack.push(t.left);

这部分是不是应该增加对称节点是否为空的判断

if (s.left != null || s.right != null) {
    stack.push(s.left);
    stack.push(t.right);
}

if (s.right != null || s.left != null) {
    stack.push(s.right);
    stack.push(t.left);
}

否则的话,如果在满足条件的情况下,stack中会增加叶子节点数量的空数据,进行多余的循环判断。

1赞

@nopsky

这么做只是把后面循环中的判断提前做了 ,不会带来多少改善。反倒增加了这里逻辑判断的复杂性。我的建议是不用在这里提前判断。

这道题的recursive的解法的空间复杂度应该是O(h)h是树的高度。只有当树非常skewed才是O(n), n是书中node的个数。

@Soliloquyyy

是的,写 O(h) 更好,但 O(n) 是没问题的。当我们说空间复杂度时,一般指的是最坏空间复杂度。

1赞