java - 找到最大的子树

Question

在面试时问这个问题，我试图了解如何解决这个问题。

在二叉树中，我试图找到最大的子树，以使所有节点包含0或2个子节点，并且所有叶节点处于同一节点级别。

例：

    1
  /     \
2        3
 \      /   \
  4    5     6
      / \   / \ 
     7   8  9   10
               /    
              11

删除1,2,4和11之后，我们得到大小为7的最大子树。

          3
        /   \
       5     6
      / \   / \ 
     7   8  9   10

现在给出一个带有左右子节点的Tree节点：

class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;
}           

我找到了一个解决方案here，但是它为我的输入提供了错误的输出。

Answer 1

//basic idea is that traveral the tree, while visiting current node, calculate the depth of the max prefect subtree with current node as the root. The depth of the final result subtree must be one of such depth(in fact, the maximum one).
class MaxPerfectSubtree{
    private int maxDepth=0;//global var for current depth of the max prefect subtree with current node as its root,updated while doing postorder traversal 
    public int solution(TreeNode root){
        postorder(root);//traversal the tree in a buttom-up style while updating the maxDepth
        return (int)Math.pow(2,maxDepth+1)-1;//with the max depth, the max node count is trival.
    }
    private int postorder(TreeNode root){//returns the depth of the max prefect subtree with root as its root.
        if(root==null)
            return 0;//

        int left=postorder(root.left);
        int right=postorder(root.right);
        int curDepth=1+Math.min(left,right);//max prefect subtree with root as its root
        if(maxDepth<curDepth)
            maxDepth=curCount;
        return curDepth;
    }
}    

注意：
只是为了证明这个想法，没有受让人认为它可以运行并产生正确的答案。



更新资料
刚刚发现，除了提供的节点数以外，还需要按顺序提供遍历树的方法（如所提供的链接所示）（这意味着也需要树）。

因此，我们可以添加一个全局TreeNode变量来记录与该全局变量maxDepth对应的根节点。

然后以top-buttom样式排序此TreeNode，并以左深度作为有序遍历函数的参数，以便一旦达到最大深度就可以中断。