LeetCode(19) -- 559, 563, 572

P559. Maximum Depth of N-ary Tree (Easy)

普通树，求最大的深度。

我的思路

递归，每个节点的最大深度，都是它所有子结点中最大的深度加1。

我的代码

public class E_559_MaximumDepthofNaryTree {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        int depth = 0;
        List<Node> children = root.children;
        for (Node child : children) {
            depth = Math.max(maxDepth(child), depth);
        }
        return depth + 1;
    }
}

97%

最优解

class Solution {
    public int maxDepth(Node root) {
        if(root == null)
            return 0;
        if(root.children.size()==0) return 1;
        int max_depth=0;
        for(int i=0;i<root.children.size();i++){
            int depth = maxDepth(root.children.get(i));
            if(depth > max_depth) max_depth = depth;
        }
        return max_depth +1;
    }
}

P563. Binary Tree Tilt (Easy)

一个树，它每个节点的tilt被定义为它左子树所有值的和跟右子树所有值的和的差的绝对值。

整个树的tilt被定义为它所有节点的tilt之和。

我的思路

这个tilt只是递归计算sum时的副产品，累加到一个全局变量即可。

我的代码

public class E_563_BinaryTreeTilt {
    int tilt = 0;
    public int findTilt(TreeNode root) {
        findSum(root);
        return tilt;
    }

    private int findSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = findSum(node.left);
        int rightSum = findSum(node.right);
        tilt += Math.abs(leftSum - rightSum);
        return node.val + leftSum + rightSum;
    }
}

98%

最优解

public class Solution {
    int result = 0;
    public int findTilt(TreeNode root) {
        post(root);
        return result;
    }

    private int post(TreeNode root) {
        if (root == null ) return 0;
        int left = post(root.left);
        int right = post(root.right);
        result += Math.abs(left - right);
        return right + left +root.val;
    }
}

P572. Subtree of Another Tree (Easy)

给两个二叉树s和t，检验t是否跟s的某一个子节点完全相同。包括s本身

我的思路

如果把s的每一个节点都去跟t进行比较，时间复杂度为m * n

我的代码

public class E_572_SubtreeOfAnotherTree {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) {
            return t == null;
        }
        if (isSame(s,t)) return true;
        return isSubtree(s.left,t) || isSubtree(s.right, t);
    }

    private boolean isSame(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
    }
}

93%

最优解

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return helper(s, t, false);
    }

    private boolean helper(TreeNode s, TreeNode t, boolean finded){
        if(s==null || t==null) return s==t;
        if(s.val != t.val){
            if(finded) return false;
            return helper(s.left, t, false)||helper(s.right, t, false);
        }
        return helper(s.left, t.left, true) && helper(s.right, t.right, true) || helper(s.left, t, false) ||helper(s.right, t, false);
    }
}

finded用来记录如果已经找到了，就不用继续再找了。