算法第十三天|二叉树

101. 对称二叉树

  public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;
        }
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right != null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }

        // 两者都不等于null
        boolean inner = compare(left.right, right.left); // 比较内侧
        boolean out = compare(left.left, right.right); // 比较外侧
        return inner && out;
    }

学习：

对称二叉树，先比较二叉树的外侧，再比较二叉树的内侧

主要是没有想到对应的方法

100. 相同的树

  public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        boolean sameTree = isSameTree(p.left, q.left);
        boolean sameTree1 = isSameTree(p.right, q.right);
        // 当前节点的值相同，并且左右子树都相同，那么认为是相同的两棵树
        return p.val == q.val && sameTree && sameTree1;
    }

这道题是对称二叉树的同类题。左子树和右子树都相等，那么两颗树自然相等了

572. 另一棵树的子树

 public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) return true;
        if (root == null) return false;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || isSameTree(root,subRoot);
    }

    private boolean isSameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false; // 某一个等于null,返回否
        }
        return root.val == subRoot.val && isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
    }

这道题不好想到的是先要遍历root的左右子树，然后再进行递归。

222.完全二叉树的节点个数

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

当前节点+左子树节点+右子树节点=总结点