力扣labuladong——一刷day50

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

最常见的，二叉树的列构造问题一般都会用到分解问题的思维模式。

一、力扣100. 相同的树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
    }
}

二、力扣1367. 二叉树中的链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if(head == null){
            return true;
        }
        if(root == null){
            return false;
        }
        if(head.val == root.val){
            if(fun(root,head)){
                return true;
            }
        }
        return isSubPath(head,root.left) || isSubPath(head,root.right);
    }
    public boolean fun(TreeNode root, ListNode head){
        if(head == null){
            return true;
        }
        if(root == null){
            return false;
        }
        if(root.val != head.val){
            return false;
        }
        return fun(root.left, head.next) || fun(root.right, head.next);
    }
}

三、力扣105. 从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return  fun(preorder,inorder, 0,preorder.length-1,0,inorder.length-1);
    }
    public TreeNode fun(int[] preorder, int[] inorder, int preLow,int preHigh, int inLow,int inHigh){
        if(preLow > preHigh){
            return null;
        }
        TreeNode cur = new TreeNode(preorder[preLow]);
        int index = 0, len = 0;
        for(int i = inLow; i <= inHigh; i ++){
            if(inorder[i] == preorder[preLow]){
                index = i;
                len = index - inLow;
                break;

            }
        }
        cur.left = fun(preorder,inorder,preLow+1,preLow+len,inLow,index-1);
        cur.right = fun(preorder,inorder,preLow+len+1,preHigh,index+1,inHigh);
        return cur;
    }
}

四、力扣654. 最大二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return fun(nums,0, nums.length-1);
    }
    public TreeNode fun(int[] nums, int low, int high){
        if(low > high){
            return null;
        }
        int index = low;
        for(int i = low; i <= high; i ++){
            index = nums[i] > nums[index] ? i:index;
        }
        TreeNode cur = new TreeNode(nums[index]);
        cur.left = fun(nums,low, index-1);
        cur.right = fun(nums,index+1,high);
        return cur;
    }
}