LeetCodeHot100 二叉树 94. 二叉树的中序遍历 104. 二叉树的最大深度 101. 对称二叉树 543. 二叉树的直径 102. 二叉树的层序遍历 108. 将有序数组转

94. 二叉树的中序遍历
https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

//    递归
//    List<Integer> resList;
//    public List<Integer> inorderTraversal(TreeNode root) {
//        resList = new ArrayList<>();
//        inorderHelper(root);
//        return resList;
//    }
//    public void inorderHelper(TreeNode node){
//        if (node == null) return;
//        inorderHelper(node.left);
//        resList.add(node.val);
//        inorderHelper(node.right);
//    }

//迭代
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while (root != null || !deque.isEmpty()){
            if (root != null){
                deque.addLast(root);
                root = root.left;
            }else {
                root = deque.pollLast();
                resList.add(root.val);
                root = root.right;
            }
        }
        return resList;
    }

104. 二叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

public int maxDepth(TreeNode root) {
        return max(root);
    }
    public int max(TreeNode node){
        if (node == null) return 0;
        int left = max(node.left);
        int right = max(node.right);
        return Math.max(left,right) + 1;
    }

总结：后序遍历 需要左右子树的信息。左右最深者+1
226. 翻转二叉树
https://leetcode.cn/problems/invert-binary-tree/?envType=study-plan-v2&envId=top-100-liked

public TreeNode invertTree(TreeNode root) {
        invertLeftAndRight(root);
        return root;
    }
    public void invertLeftAndRight(TreeNode node){
        if (node == null) return;
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        invertLeftAndRight(node.left);
        invertLeftAndRight(node.right);
    }

总结：前序遍历，每次交换左和右
101. 对称二叉树
https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked

public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }
    public boolean compare(TreeNode left,TreeNode right){
        if (left == null && right != null) return false;
        if (left != null && right == null) return false;
        if (left == null && right == null) return true;
        if (left.val != right.val) return false;
        boolean out = compare(left.left,right.right);
        boolean in = compare(left.right,right.left);
        return in && out;
    }

总结：递归函数要两个节点，两个节点就是要比对的节点，前序，每次结束之后都去看外侧和内侧。
543. 二叉树的直径
https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

int diameter;
    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        diameterHelper(root);
        return diameter;
    }
    public int diameterHelper(TreeNode node){
        if (node == null) return 0;
        int depthLeft = diameterHelper(node.left);
        int depthRight = diameterHelper(node.right);
        diameter = Math.max(depthLeft + depthRight,diameter);
        return Math.max(depthLeft,depthRight) + 1;
    }

总结：后序，每个节点当前的直径就是当前的左子树深度+右子树深度。
102. 二叉树的层序遍历
https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-100-liked

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null) return resList;
        deque.addLast(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            List<Integer> tempList = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.pollFirst();
                tempList.add(node.val);
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
            }
            resList.add(new ArrayList<>(tempList));
        }
        return resList;
    }

总结：。。。
108. 将有序数组转换为二叉搜索树
https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int[] nums,int start,int end){
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode treeNode = new TreeNode(nums[mid]);
        treeNode.left = helper(nums,start,mid - 1);
        treeNode.right = helper(nums,mid + 1,end);
        return treeNode;
    }

总结：二分查找去构造新节点。
98. 验证二叉搜索树
https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        if (left == false) return false;
        if (pre != null && root.val <= pre.val){
            return false;
        }
        pre = root;
        boolean right = isValidBST(root.right);
        return right;
    }

总结：我们知道二叉搜索树的中序遍历是从小到大，那只要中序遍历的时候每次看当前节点和前一个节点的值是否满足当前节点>上一个几点即可判断是不是二叉搜索树。
230. 二叉搜索树中第K小的元素
https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-100-liked

    int res = 0;
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        inorder(root);
        return res;
    }
    public void inorder(TreeNode node){
        if (node == null) return;
        inorder(node.left);
        if (k == 1) {
            res = node.val;
            k--;
            return;
        }else {
            k--;
        }
        inorder(node.right);
    }

总结：指定一个计数器，每然后中序遍历，到计数器的时候就放进res中
199. 二叉树的右视图
https://leetcode.cn/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-100-liked

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> resList = new ArrayList<>();
        if (root == null) return resList;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode treeNode = deque.pollFirst();
                if (i == len - 1) resList.add(treeNode.val);
                if (treeNode.left != null) deque.addLast(treeNode.left);
                if (treeNode.right != null) deque.addLast(treeNode.right);
            }
        }
        return resList;
    }

总结：层序遍历，拿每层的最后一个。
114. 二叉树展开为链表
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

public void flatten(TreeNode root) {
		if(root==null) {
			return;
		}
		LinkedList<TreeNode> res = new LinkedList<TreeNode>();
		//前序遍历整棵二叉树
		dfs(root,res);
		TreeNode head = res.removeFirst();
		head.left = null;
		//遍历链表，将链表中的TreeNode节点前后串联起来
		while(res.size()>0) {
			TreeNode tmp = res.removeFirst();			
			tmp.left = null;
			head.right = tmp;
			head = head.right;
		}	
	}
	
	//前序遍历整棵二叉树，并将遍历的结果放到数组中
	void dfs(TreeNode root, List<TreeNode> res) {
		if(root==null) {
			return;
		}
		res.add(root);
		dfs(root.left,res);
		dfs(root.right,res);
	}

总结：先序遍历每个节点，存下来，再操作。