二叉樹之最大搜尋二叉樹

有一棵二叉樹，其中所有節點的值都不一樣,找到含有節點最多 的搜尋二叉子樹,并傳回這棵子樹的頭節點.

給定二叉樹的頭結點root，請傳回所求的頭結點,若出現多個節點最多的子樹，傳回頭結點權值最大的。

分析：

以節點node為頭的樹種，最大搜尋二叉樹隻可能來自以下兩種情況。

1.如果來自node左子樹上的最大搜尋二叉樹是以node.left為頭的；來自node右子樹上的最大搜尋二叉樹是以node.right為頭的；node左子樹上的最大搜尋二叉子樹的最大值小于node.value;node右子樹上的最大搜尋二叉樹的最小值大于node.value,那麼以節點node為頭的整個數都是搜尋二叉樹。

2.如果不滿足第一種情況，說明一節點node為頭的整棵樹不能連城搜尋二叉樹。這種情況下，以node為頭的樹上的最大搜尋二叉樹來自node為頭的樹上的最大搜尋二叉子樹是來自node左子樹上的最大搜尋二叉樹和來自node右子樹上的最大二叉樹子樹中節點較多的那個。

3.整個過程後序周遊：周遊到目前節點即為cur,先周遊cur左子樹收集四個資訊，分别是左子樹上最大搜尋二叉樹子頭結點LBST，節點數LSize，最小值LMin和最大值LMax.再周遊cur右子樹收集四個資訊，分别是右子樹上最大搜尋二叉樹子頭結點RBST，節點數RSize，最小值RMin和最大值RMax

4.根據3中的資訊，判斷是否滿足第一種情況，如果滿足就傳回cur,如果滿足第二種就傳回LBST和RBST中較大一個。

代碼如下

import java.util.*;

public class MaxSubtree {

     private int nodeSize=0;

    private int minVal=Integer.MAX_VALUE;

    private int maxVal=Integer.MIN_VALUE;

    public TreeNode getMax(TreeNode root) {

        // write code here

        return posOrder(root);

    }

  public TreeNode posOrder(TreeNode head){

      if(head==null){

           minVal=Integer.MAX_VALUE;

             maxVal=Integer.MIN_VALUE;

          nodeSize=0;

          return null;

      }

      int value=head.val;

      TreeNode left=head.left;

      TreeNode right=head.right;

      TreeNode lBST=posOrder(left);

      int lNodeSize=nodeSize;

      int lminVal=minVal;

      int lmaxVal=maxVal;

      TreeNode rBST=posOrder(right);

      int rNodeSize=nodeSize;

      int rminVal=minVal;

      int rmaxVal=maxVal;

      minVal=Math.min(value,lminVal);

      maxVal=Math.max(value,rmaxVal);

      if(left==lBST&&right==rBST&&lmaxVal<value&&rminVal>value){

          nodeSize=lNodeSize+rNodeSize+1;

          return head;

      }

      nodeSize=Math.max(lNodeSize,rNodeSize);

      return lNodeSize>rNodeSize?lBST:rBST;

  }

}