LeetCode刷题笔记之二叉树（三）

一、寻找特定节点

1. 404【左叶子之和】

• 题目： 给定二叉树的根节点 root ，返回所有左叶子之和。
• 代码：

class Solution {public int sumOfLeftLeaves(TreeNode root) {//左叶子不止是最左边的叶子，而是二叉树中每个节点的左叶子//每棵树的左叶子之和=左子树左叶子之和+右子树左叶子之和//其中，左子树可能是一个叶子节点，它的左叶子之和就是它本身if(root == null) return 0;int leftSum = 0;if(root.left!=null && root.left.left==null && root.left.right==null){leftSum = root.left.val;}else{leftSum = sumOfLeftLeaves(root.left);}int right = sumOfLeftLeaves(root.right);return leftSum+right;}
}

2. 513【找树左下角的值】

• 题目： 给定一个二叉树的 根节点 root，请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。
• 代码：

class Solution {public int findBottomLeftValue(TreeNode root) {//最底层最左边，也就是层序遍历最后一层的第一个节点Deque<TreeNode> queue = new ArrayDeque<>();queue.offer(root);TreeNode ansNode = root;while (!queue.isEmpty()){int len = queue.size(); //必须提前声明，因为每次循环queue的长度都会变化for (int i = 0; i < len; i++) {TreeNode tempNode = queue.poll();if(i == 0){ansNode = tempNode;}if(tempNode.left != null){queue.offer(tempNode.left);}if(tempNode.right != null){queue.offer(tempNode.right);}}}return ansNode.val;}
}

二、构造二叉树

1. 106【从中序与后序遍历序列构造二叉树】

• 题目： 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
• 代码：

class Solution {public TreeNode buildSubTree(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart,int postEnd){//如果后序遍历数组为空，则表示该部分节点构建完成if(postEnd == postStart){return null;}TreeNode root = new TreeNode(postorder[postEnd-1]);int middle;for (middle = inStart; middle < inEnd ; middle++) {if(inorder[middle] == postorder[postEnd-1]){break;}}//注意后续遍历数组的分割点TreeNode leftNode = buildSubTree(inorder,inStart,middle,postorder,postStart,postStart+middle-inStart);TreeNode rightNode = buildSubTree(inorder,middle+1,inEnd,postorder,postStart+middle-inStart,postEnd-1);root.left = leftNode;root.right = rightNode;return root;}public TreeNode buildTree(int[] inorder, int[] postorder) {//已知中序遍历和前序遍历可以确定唯一二叉树//已知中序遍历和后序遍历可以确定唯一二叉树//因为后序遍历为左右根，所以后序遍历数组中最后一个元素为二叉树的根//在中序遍历数组中，根的左边为根的左子树，根的右边为根的右子树//因为中序遍历为左根右，所以在中序遍历中根的左边有n个节点，//在后序遍历中最左边n个节点构成根的左子树if(inorder.length==0 || postorder.length==0) return null;//首先，找到根，根据根划分后序遍历数组//然后，根据后序遍历数组划分中序遍历数组TreeNode root = buildSubTree(inorder,0,inorder.length,postorder,0,postorder.length);return root;}
}

2. 105【从前序与中序遍历序列构造二叉树】

• 题目： 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
• 代码：

class Solution {public TreeNode buildSubTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){if(preEnd == preStart){return null;}TreeNode root = new TreeNode(preorder[preStart]);int middle;for(middle=inStart;middle<inEnd;middle++){if(preorder[preStart] == inorder[middle]){break;}}TreeNode leftNode = buildSubTree(preorder,preStart+1,preStart+1+middle-inStart,inorder,inStart,middle);TreeNode rightNode = buildSubTree(preorder,preStart+1+middle-inStart,preEnd,inorder,middle+1,inEnd);root.left = leftNode;root.right = rightNode;return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {//与上一题相似，只是这里在前序遍历数组由前向后遍历if(preorder.length==0 || inorder.length==0){return null;}return buildSubTree(preorder,0,preorder.length,inorder,0,inorder.length);}
}

3. 654【最大二叉树】

• 题目： 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
  （1）创建一个根节点，其值为 nums 中的最大值。
  （2）递归地在最大值 左边 的 子数组前缀上 构建左子树。
  （3）递归地在最大值 右边 的 子数组后缀上 构建右子树。
  （4）返回 nums 构建的 最大二叉树 。
• 代码：

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {//首先，找到最大值，根据最大值划分数组//最大值左边组成左子树，最大值右边组成右子树，最大值构建根//左子树，右子树递归构建//递归时需要传入所有要进行构建树的值，因此需要return constructTree(nums,0,nums.length);}public TreeNode constructTree(int[] nums,int start, int end){if(end <= start){return null;}int max = nums[start];int index = start;for (int i = start; i < end; i++) {if(nums[i]>max){index = i;max = nums[i];}}TreeNode root = new TreeNode(nums[index]);TreeNode leftNode = constructTree(nums,start,index);TreeNode rightNode = constructTree(nums,index+1,end);root.left = leftNode;root.right = rightNode;return root;}
}

4. 617【合并二叉树】

• 题目： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
• 代码：

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//在一棵树的基础上操作，直接加上另一棵树该位置的值，如果为null，值为0//采用前序遍历，终止条件为一棵树遍历完成if(root1 == null) return root2;if(root2 == null) return root1;root1.val = root1.val+root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}
}