Tree Problem

Algorithm

---

Binary Tree Content:

• 1.求二叉树中的节点个数: getNodeNumRec（递归），getNodeNum（迭代）
• 2.求二叉树的深度: getDepthRec（递归），getDepth
• 3.前序遍历，中序遍历，后序遍历: preorderTraversalRec, preorderTraversal, inorderTraversalRec, postorderTraversalRec (https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2)
• 4.分层遍历二叉树（按层次从上往下，从左往右）: levelTraversal, levelTraversalRec（递归解法！）
• 5.将二叉查找树变为有序的双向链表: convertBST2DLLRec, convertBST2DLL
• 6.求二叉树第K层的节点个数：getNodeNumKthLevelRec, getNodeNumKthLevel
• 7.求二叉树中叶子节点的个数：getNodeNumLeafRec, getNodeNumLeaf
• 8.判断两棵二叉树是否相同的树：isSameRec, isSame
• 9.判断二叉树是不是平衡二叉树：isAVLRec
• 10.1 求二叉树的镜像（破坏和不破坏原来的树两种情况）：mirrorRec, mirrorCopyRec

• 10.2 判断两个树是否互相镜像：isMirrorRec

• 11.求二叉树中两个节点的最低公共祖先节点：getLastCommonParent, getLastCommonParentRec, getLastCommonParentRec2

• 12.求二叉树中节点的最大距离：getMaxDistanceRec
• 13.由前序遍历序列和中序遍历序列重建二叉树：rebuildBinaryTreeRec
• 14.判断二叉树是不是完全二叉树：isCompleteBinaryTree, isCompleteBinaryTreeRec
• 15.Path Sum (Root-to-leaf) (node-to-node)
• 16.Subtree Match in a Huge Tree

1. The Number of Nodes in a Tree

Recursion Method: 

            int NodeNumRec(TreeNode node):
                    if(node==null):
                        return 0;
                    return NodeNumRec(node.left)+NodeNumRec(node.right)+1;

Iterative Method:

            int NodeNumItr(TreeNode node):
                    if(node==null):
                        return 0;
                    int nodeNum = 0;
                    Queue<TreeNode> q = new Queue<TreeNode>();
                    q.add(node);
                    while(!q.isEmpty()):
                        TreeNode qnode = q.remove();
                        nodeNum++;
                        if(qnode.left!=null):
                            q.add(qnode.left);
                        if(qnode.right!=null):
                            q.add(qnode.right);
                    return nodeNum;

2. The Depth of Tree:

Recursion Method:

            int TreeDepth(TreeNode node):
                    if(node==null):
                            return 0;
                    return Math.max(TreeDepth(node.left),TreeDepth(node.right))+1;

Iterative Method:

            int TreeDepth(TreeNode node):
                    if(node==null):
                        return 0;
                    // remember these record variables
                    int depth = 0;                          
                    int currentLevelNodes = 1;       
                    int nextLevelNodes = 0;   
                    Queue<TreeNode> q = new Queue<TreeNode>();
                    q.add(node);
                    while(!q.isEmpty()):
                        TreeNode qnode = q.remove();
                        currentLevelNodes--;
                        if(qnode.left!=null):
                            q.add(qnode.left);
                            nextLevelNodes++;
                        if(qnode.right!=null):
                            q.add(qnode.right);
                            nextLevelNodes++;
                        if(currentLevelNodes==0):
                            depth++;
                            currentLevelNodes = nextLevelNodes;
                            nextLevelNodes = 0;
                    return depth;

####3. Tree Traversal:

PreOrder: - Recursion

            List<TreeNode> list = new ArrayList<TreeNode>();
            void preorder(TreeNode node):
                    if(node==null):
                        return;
                    list.add(node);
                    preorder(node.left);
                    preorder(node.right);

PreOrder: - Iterative
 关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子  

            List<TreeNode> list = new ArrayList<TreeNode>();
            void preorder(TreeNode node):
                    if(node==null):
                        return;
                    Stack<TreeNode> s = new Stack<TreeNode>();
                    s.push(node);
                    while(!s.isEmpty()):
                        TreeNode snode = s.pop();
                        list.add(snode);
                        if(snode.right!=null):
                            s.push(snode.right);
                        if(snode.left!=null):
                            s.push(snode.left);

InOrder: - Recursion

            List<TreeNode> list = new ArrayList<TreeNode>();
            void inorder(TreeNode node):
                    if(node==null):
                        return;
                    inorder(node.left);
                    list.add(node);             
                    inorder(node.right);

InOrder: - Iterative

            List<TreeNode> list = new ArrayList<TreeNode>();
            void inorder(TreeNode node):
                    if(node==null):
                        return;
                    Stack<TreeNode> s = new Stack<TreeNode>();
                    TreeNode cur = root;
                    while(true):
                        while(cur!=null):
                            s.push(cur);
                            cur = cur.left;
                        if(!s.isEmpty()):
                            break;
                        cur = s.pop();
                        list.add(cur);
                        cur = cur.right;

PostOrder: - Recursion

            List<TreeNode> list = new ArrayList<TreeNode>();
            void postorder(TreeNode node):
                    if(node==null):
                        return;
                    postorder(node.left);
                    postorder(node.right);
                    list.add(node);             

PostOrder: - Iterative

            List<TreeNode> list = new ArrayList<TreeNode>();
            void postorder(TreeNode node):
                    if(node==null):
                        return;
                    Stack<TreeNode> s = new Stack<TreeNode>();
                    Stack<TreeNode> output = new Stack<TreeNode>();
                    s.push(node);
                    while(!s.isEmpty()):
                        TreeNode cur = s.pop();
                        output.push(cur);
                        if(cur.left!=null):
                            s.push(cur.left);   
                        if(cur.right!=null):
                            s.push(cur.right);
                    while(!output.isEmpty())
                        list.add(output.pop());

5. Level Order:

LevelOrder: - Recursion

            void levelTraversalRec(TreeNode root): 
                    ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();  
                    dfs(root, 0, ret);  
            void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret):  
                    if(root == null); 
                        return;   
                    // 添加一个新的ArrayList表示新的一层  
                    if(level >= ret.size()):  
                        ret.add(new ArrayList<Integer>());  
                    ret.get(level).add(root.val);   // 把节点添加到表示那一层的ArrayList里  
                    dfs(root.left, level+1, ret);       // 递归处理下一层的左子树和右子树  
                    dfs(root.right, level+1, ret);  

LevelOrder: - Iterative

            List<List<TreeNode>> res = new ArrayList<List<TreeNode>>();
            void LevelOrder(TreeNode root):
                    if(root==null)
                        return;
                    int curLevel = 1;
                    int nextLevel = 0;
                    Queue<TreeNode> q = new Queue<TreeNode>();
                    List<TreeNode> row = new ArrayList<TreeNode>();
                    q.push(root);
                    while(!q.isEmpty()):
                        TreeNode qnode = q.remove();
                        row.add(qnode);
                        curLevel--;
                        if(qnode.left!=null):
                            q.push(qnode.left);
                            nextLevel++;
                        if(qnode.right!=null):
                            q.push(qnode.right);
                            nextLevel++;
                        if(curLevel==0):
                            curLevel = nextLevel;
                            curLevel = 0;
                            res.add(row);
                            row = new ArrayList<TreeNode>();
                    return res;

6. Convert BST to Doubly Linked List： -recursion

            TreeNode convertBST2DLL(TreeNode root):
                    root = convertBST2Sub(root);
                    while(root.left!=null):
                        root = root.left;
                    return root;
            TreeNode convertBST2Sub(TreeNode root):
                    if(root==null||root.left==null||root.right==null):
                        return root;
                    TreeNode cur= null;
                    if(root.left!=null):
                        cur = convertBST2Sub(root.left); // get bottom left node
                        while(cur.right!=null):
                            cur = cur.right;
                        cur.right = root;
                        root.left = cur;
                    if(root.right!=null):
                        cur = convertBST2Sub(root.right); // get bottom right node
                        while(cur.right!=null):
                            cur = cur.right;
                        cur.right = root;
                        root.right = cur;
                    return root;

-iterative

            if(root==null):
                return null;
            Stack<TreeNode> stack = new Stack<TreeNode>(); 
            TreeNode cur = root;
            TreeNode prev = null;
            TreeNode head = null;
            while(true):
                while(cur!=null):
                    stack.push(cur);
                    cur = cur.left;
                if(stack.isEmpty())
                    break;
                cur = stack.pop();
                if(old!=null):
                    old.right = cur;
                if(head==null): head = cur;
                old = cur;
                cur = cur.right;
            return head;

7. Level K Nodes Number:

- Recursion

            int getNodeNumKthLevelRec(TreeNode root, int k)
                    if(root==null || k<1)
                        return 0;
                    if(k==1)
                        return 1;
                    int numLeft = getNodeNumKthLevelRec(root.left, k - 1);      // 求root左子树的k-1层节点数  
                    int numRight = getNodeNumKthLevelRec(root.right, k - 1);    // 求root右子树的k-1层节点数  
                    return numLeft + numRight;  

 - Iterative

            int getNodeNumKthLevelRec(TreeNode root, int k) 
                    if(root==null):
                        return 0;
                    Queue<TreeNode> q = new Queue<TreeNode>();
                    q.add(root);
                    int curLevel = 1;
                    int nextLevel = 0;
                    int i = 0;
                    while(!q.isEmpty()&&i<k):
                        TreeNode cur = q.remove();
                        curLevel--;
                        if(cur.left!=null):
                            q.add(cur.left);
                            nextLevel++;
                        if(cur.right!=null):
                            q.add(cur.right);
                            nextLevel++;
                        if(curLevel==0):
                            curLevel = nextLevel;
                            curLevel = 0;
                            i++;
                    return curLevel;

8. The number of leaves:

- iterative

            int getLeavesNum(TreeNode root):
                    if(root==null):
                        return 0;
                    if(root.left==null&&root.right==null):
                        return 1;
                    return getLeavesNum(root.left)+getLeavesNum(root.right);

- recursion

            int getLeavesNum(TreeNode root):
                    if(root==null):
                        return 0;
                    int leafNum = 0;
                    Queue<TreeNode> q = new Queue<TreeNode>();
                    q.push(root);
                    while(!q.isEmpty()):
                        TreeNode node = q.pop();
                        if(cur.left != null):               // 如果有左孩子，加到队尾  
                            queue.add(cur.left);  
                        if(cur.right != null):              // 如果有右孩子，加到队尾  
                            queue.add(cur.right);  
                        if(cur.left==null && cur.right==null):          // 叶子节点  
                            leafNodes++;  
                    return leafNum;

9. isTheSameTree:

-recursion

            boolean isSameRec(TreeNode r1, TreeNode r2):
                    if(r1==null&&r2==null)
                        return true;
                    else if(r1==null||r2==null)
                        return false;
                    if(r1!=r2)
                        return false;
                    return isSameRec(r1.left,r2.right)&&isSameRec(r1.right,r2.right);

-iterative

            boolean isSame(TreeNode r1, TreeNode r2) {  
                    // 如果两个树都是空树，则返回true  
                    if(r1==null && r2==null):  
                        return true;  
                    // 如果有一棵树是空树，另一颗不是，则返回false  
                    if(r1==null || r2==null):  
                        return false;  
                    Stack<TreeNode> s1 = new Stack<TreeNode>();  
                    Stack<TreeNode> s2 = new Stack<TreeNode>();  
                    s1.push(r1);  
                    s2.push(r2);  
                    while(!s1.isEmpty() && !s2.isEmpty()):  
                        TreeNode n1 = s1.pop();  
                        TreeNode n2 = s2.pop();  
                        if(n1==null && n2==null):  
                            continue;  
                        else if(n1!=null && n2!=null && n1.val==n2.val):  
                            s1.push(n1.right);  
                            s1.push(n1.left);  
                            s2.push(n2.right);  
                            s2.push(n2.left);  
                        else:  
                            return false;  
                    return true;  

10. Balanced Tree Check:

- recursion

            boolean isAVLRec(TreeNode root):
                    if(root==null)
                        return true;
                    if(Math.abs(getDepth(root.left),getDepth(root.right)>1)
                        return false;
                    return isAVLRec(root.left)&&isAVLRec(root.right);
            int getDepth(TreeNode node):
                    if(node==null)
                        return 0;
                    return Math.max(getDepth(node.left),getDepth(node.right))+1;

11. Mirror Tree:

    - based on original tree (recursion)

            TreeNode mirrorRec(TreeNode root):
                    if(root==null)
                        return null;
                    // TreeNode newNode = new TreeNode(root.val);
                    TreeNode left = mirrorRec(root.left);
                    TreeNode right = mirrorRec(root.right);
                    // newNode.left = right;
                    // newNode.right = left;
                    root.left = right;
                    root,right = left;
                    // return newNode;
                    return root;

    - based on original tree (iterative)

            void mirrorItr(TreeNode root):
                    if(root==null)
                        return null;
                    Stack<TreeNode> s = new Stack<TreeNode>();
                    s.push(root);
                    // Stack<TreeNode> newStack = new Stack<TreeNode>();
                    // TreeNode newRoot = new TreeNode(root.val);  
                    // newStack.push(newRoot); 
                    while(!s.isEmpty()):
                        TreeNode cur = s.pop();
                        // do exchange!
                        TreeNode tmp = cur.left;
                        cur.left = cur.right;
                        cur.right = tmp;
                        if(cur.right!=null)
                            s.push(cur.right);
                        if(cur.left!=null)
                            s.push(cur.left);
                        // TreeNode newCur = newStack.pop(); 
                        /** if you want construct new mirror tree!
                        if(cur.right != null):  
                            stack.push(cur.right);  
                            newCur.left = new TreeNode(cur.right.val);  
                            newStack.push(newCur.left);  
                        if(cur.left != null):  
                            stack.push(cur.left);  
                            newCur.right = new TreeNode(cur.left.val);  
                            newStack.push(newCur.right);
                        **/

12. Last Common Anster:

1. • Easy Understand Version
     if two nodes are in the differen subtree return root as the last common anster
     if two nodes are in the same left subtree or right subtree, addressing in subtree recusively

            TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2):
                    if(findNodeRec(root.left,n1)):
                        if(findNodeRec(root.right,n2))
                            return root;
                        else
                            getLastCommonParentRec(root.left,n1,n2);
                    else
                        if(findNodeRec(root.left,n2))
                            return root;
                        else
                            getLastCommonParentRec(root.right,n1,n2);
            boolean findNodeRec(TreeNode root, TreeNode n):
                    if(root==null || node == null)
                        return false;
                    if(root == n)
                        return true;
                    return findNodeRec(root.left,n)||findNodeRec(root.right,n);
                    /**
                    boolean found = findNodeRec(root.left, node);  
                    if (!found):       // 如果查找不到，再在右子树中查找  
                        found = findNodeRec(root.right, node);   
                    return found;
                    **/

1. • Concise Recursion Version:
     // get the path from root to the node
     // iterate two paths with comparing nodes difference

            TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2):
                    if(root==null): return null;
                    if(root.equals(n1)||root.equals(n2)):
                        return root;
                    TreeNode left = getLastCommonParentRec(root.left,n1,n2);
                    TreeNode right = getLastCommonParentRec(root.right,n1,n2);
                    if(left!=null&&right!=null)
                        return root;
                    if(left!=null)
                        return left;
                    return right;

1. Non-recursion but require resurive helper function
   // get the path from root to the node
   // iterate two paths with comparing nodes difference

            TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2):
                    if(root==null||n1==null||n2==null):
                        return null;
                    ArrayList<TreeNode> p1 = new ArrayList<TreeNode>();
                    ArrayList<TreeNode> p2 = new ArrayList<TreeNode>();  
                    boolean res1 = getPath(root, n1, p1);  
                    boolean res2 = getPath(root, n2, p2);  
                    if (!res1 || !res2): 
                        return null;   
                    TreeNode last = null;  
                    Iterator<TreeNode> iter1 = p1.iterator();  
                    Iterator<TreeNode> iter2 = p2.iterator();  
                    while (iter1.hasNext() && iter2.hasNext()):  
                        TreeNode tmp1 = iter1.next();  
                        TreeNode tmp2 = iter2.next();  
                        if (tmp1 == tmp2): 
                            last = tmp1;  
                        else: // 直到遇到非公共节点  
                            break;  
                    return last; 
            boolean getPath(TreeNode root, TreeNode n, ArrayList<TreeNode> p): // backtracking
                    if(root==null) return false;
                    p.add(root);
                    if(root == n)
                        return true;
                    boolean found = getPath(root.left,n,p);
                    if(!found)
                        found = getPath(root.right,n,p);
                    if(!found)
                        p.remove(root);
                    return found;

####14. Max Distance between two leaves: (node1 -> root -> node2 or node1 -> nodes... -> node2)

            class Result:  //private class for result 
                    int maxDistance;  
                    int maxDepth;  
                    public Result(): // non argument constructor
                    public Result(int maxDistance, int maxDepth): // two argument constructor  
                        this.maxDistance = maxDistance;  
                        this.maxDepth = maxDepth;  
            Result getMaxDistanceRec(TreeNode root):
                    if(root == null):
                        Result empty = new Result(0,-1);
                        return empty;
                    Result lmd = getMaxDistanceRec(root.left);
                    Result rmd = getMaxDistanceRec(root.right);
                    Result res = new Result();
                    res.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth)+1;
                    res.maxDistance = Math.max(lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance))；
                    return res;

15.Binary Tree Construction:

        - preorder & inorder

            HashMap<Integer, Intger> inorderMap= new HashMap<Integer, Intger>();
            TreeNode rebuildBinaryTreeRec(List<Integer> preOrder, List<Integer> inOrder):
                    for(int i=0;i<inOrder.size();i++):
                            inorderMap.put(inOrder.get(i).val,i);
                    return construct(preOrder,inOrder,0,preOrder.size()-1,0,inOrder.size()-1)
            TreeNode construct(List<Integer> preOrder, List<Integer> inOrder, int pstart, int pend, int istart, int iend):
                    if(pstart>pend||istart > iend)
                        return null;
                    TreeNode  root = preOrder.get(pstart);
                    int index = map.get(root.val);
                    root.left = construct(preOrder,inOrder,pstart+1,pstart+index-istart, istart,index-1);
                    root.right = construct(preOrder,inOrder,pstart+index-istart+1,pend,index+1,iend);
                    return root;

        - postorder & inorder

            HashMap<Integer, Intger> inorderMap= new HashMap<Integer, Intger>();
            TreeNode rebuildBinaryTreeRec(List<Integer> postOrder, List<Integer> inOrder):
                    for(int i=0;i<inOrder.size();i++):
                            inorderMap.put(inOrder.get(i).val,i);
                    return construct(postOrder,inOrder,0,postOrder.size()-1,0,inOrder.size()-1)
            TreeNode construct(List<Integer> postOrder, List<Integer> inOrder, int pstart, int pend, int istart, int iend):
                    if(pstart>pend||istart > iend)
                        return null;
                    TreeNode  root = postOrder.get(pend);
                    int index = map.get(root.val);
                    root.left = construct(preOrder,inOrder,pstart,pstart+index-istart, istart,index-1);
                    root.right = construct(preOrder,inOrder,pend+index-iend,pend-1,index+1,iend);
                    return root;

16.Complete Binary Tree: 当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树

                -- Iterative:

                    boolean haveNoChild(TreeNode root):
                            if(root.left!=null||root.right!=null)
                                return false;
                            else
                                return true;
                    boolean isCompleteBT(TreeNode root):
                            if(root == null):
                                return false;
                            Queue<TreeNode> q = new Queue<TreeNode>();
                            q.add(root);
                            boolean noChild = false; // as the flag
                            boolean result = true;
                            while(!q.isEmpty()):
                                TreeNode cur = q.remove();
                                if(noChild):
                                    if(cur.left!=null||cur.right!=null):
                                        result = false;
                                        break;
                                else
                                    if(cur.left!=null && cur.right!=null):
                                        q.add(cur.left);  
                                        q.add(cur.right);
                                    else if(cur.left!=null && cur.right==null): 
                                        // 如果左子树非空但右子树为空，说明已经出现空节点，之后必须都为空子树  
                                        noChild = true;  
                                        q.add(cur.left);
                                    else if(cur.left==null && cur.right!=null):
                                        // 如果左子树为空但右子树非空，说明这棵树已经不是完全二叉完全树
                                        result = false;  
                                        break;
                                    else
                                        noChild = true;
                            return result;

Complete Binary Tree and Perfect Binary Tree:

                    class Pair:
                            int height;
                            boolean isFull;
                            public Pair(int height, boolean isFull): // two argument constructor
                                this.height = height;
                                this.isFull = isFull;
                            boolean equalsTo(Pair obj):
                                return this.height == obj.height && this.isFull == obj.isFull;
                    boolean isPerfectTree(TreeNode root):
                            return isCompleteBinaryTreeSubRec(root).isFull; 
                    boolean isCompleteBinaryTreeRec(TreeNode root):
                            return isCompleteBinaryTreeSubRec(root).height != -1; 
                    Pair isCompleteBinaryTreeSubRec(TreeNode root):
                            if(root == null)
                                return Pair(0,true);
                            Pair left = isCompleteBinaryTreeSubRec(root.left);
                            Pair right = isCompleteBinaryTreeSubRec(root.right);
                             // 左树满节点，而且左右树相同高度，则是唯一可能形成满树（若右树也是满节点）的情况  
                            if(left.isFull && left.height == right.height):  
                                return new Pair(1+left.height, right.isFull);
                            // 左树非满，但右树是满节点，且左树高度比右树高一  
                            // 注意到如果其左树为非完全树，则它的高度已经被设置成-1，  
                            // 因此不可能满足第二个条件！  
                            if(right.isFull && left.height==right.height+1):  
                                return new Pair(1+left.height, false); 
                            // 其他情况都是非完全树，直接设置高度为-1  
                            return new Pair(-1, false);

17. Path Sum -Start from any node:

            void findSum(TreeNode head, int num, ArrayList<Integer> buffer, int level):
                    if(head==null): return;
                    int tmp = sum;
                    buffer.add(head.val);
                    for(int i=level;i>-1;i--):   //check the path by buffer!
                            tmp -= buffer.get(i);
                            if(tmp == 0):
                                print(buffer,i,level);
                    ArrayList<Integer> c1 = (ArrayList<Integer>)buffer.clone();
                    ArrayList<Integer> c2 = (ArrayList<Integer>)buffer.clone();
                    findSum(head.left, sum, c1, level+1);
                    findSum(head.right, sum, c2, level+1);
    - Start from root:
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            ArrayList<ArrayList<Integer>> findSum(TreeNode root, int sum):
                    if(root==null)
                        return res;
                    ArrayList<Integer> row = new ArrayList<Integer>();
                    row.add(root.val);
                    return findSumHelper(row, root, sum -root.val);
            void findSumHelper(ArrayList<Integer> row, TreeNode node, int sum):
                    if(node == null):
                            return;
                    if(node.left==null&&node.right==null&&sum-node.val==0):
                            res.add(new ArrayList<Integer>(row));
                            return;
                    if(node.left!=null&&node.right==null):
                            row.add(node.left.val);
                            findSumHelper(row, node.left, sum-node.left.val);
                            row.remove(row.size()-1);
                    if(node.right!=null&&node.left==null):
                            row.add(node.right.val);
                            findSumHelper(row, node.right, sum-node.right.val);
                            row.remove(row.size()-1);
 Match Subtree:
    // check if the subtree is null, return true if it is null;
    // check if main tree contain the root node of subtree
    // if ant node match in two trees begin to match all node under subtree with comparing the main tree
            boolean containsTree(TreeNode mainRoot, TreeNode subRoot):
                            if(subRoot == null): return true;
                            else
                                return subtree(mainRoot,subRoot);
                    boolean subtree(TreeNode mainRoot, TreeNode subRoot):
                            if(mainRoot == null):
                                return false;
                            if(mainRoot == subroot):
                                if(matchTree(mainRoot, subRoot)):
                                    return true;
                            return subtree(mainRoot.left,subRoot)||subtree(mainRoot.right,subRoot);
                    boolean matchTree(TreeNode mainRoot, TreeNode subRoot):
                            if(subRoot == null && mainRoot == null)
                                return true;
                            if(mainRoot == null || subRoot == null)
                                return false; the main tree is empty or subtree not found
                            if(mainRoot.val!= subRoot.val)
                                return false;
                return matchTree(mainRoot.left,subRoot.left)&&matchTree(mainRoot.right,subRoot.right);