前言
本文是跟着代码随想录的二叉树顺序进行刷题并编写的 代码随想录
二叉树的题目较多，就多分了几次写，这是第三篇
这是力扣刷算法的其他文章链接：刷算法Leetcode文章汇总
二叉树篇Ⅲ
（1）226. 翻转二叉树
dfs，对每个节点反转左右子树
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null)return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left=right;
root.right=left;
return root;
}
}
（2）101. 对称二叉树
①dfs，左右子树同时递归并进行判断
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isSymmetricNode(root.left, root.right);
}
public boolean isSymmetricNode(TreeNode node1, TreeNode node2){
if(node1 == null && node2 == null) return true;
if(node1 == null || node2 == null) return false;
if(node1.val != node2.val) return false;
return isSymmetricNode(node1.left, node2.right)
&&isSymmetricNode(node1.right,node2.left);
}
}
②bfs+队列，左右比较节点依次入队。注意空节点也要加入队列，代表左右位置
注意：ArrayDeque线程不安全不能加入空节点，因此使用LinkedList实现队列
class Solution {
private Deque queue;
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
queue = new LinkedList();
queue.addLast(root.left);
queue.addLast(root.right);
while(!queue.isEmpty()){
TreeNode node1 = queue.pollFirst(), node2 = queue.pollFirst();
if(node1 == null && node2 == null) continue;
if(node1 == null || node2 == null) return false;
if(node1.val != node2.val) return false;
queue.addLast(node1.left);
queue.addLast(node2.right);
queue.addLast(node1.right);
queue.addLast(node2.left);
}
return true;
}
}
（3）222. 完全二叉树的节点个数
①bfs+队列，同102题（可见上一篇），层序遍历计数即可
②dfs，同102题（可见上一篇），递归左右节点计数
③二分查找+位运算，使用二分查找确定分支，位运算选择左右节点。
具体操作：先找最左节点确定层数level（根为第零层），总节点数min=1<<(level),max=((1<<(level+1))-1，在min和max中进行二分查找。若mid处的node空，取左半部分迭代，若node不空取右半部分迭代；确定level层某个节点是否存在：node从根开始，根据与half=1<<(level-1)进行位与，即从左第二位开始取，为0左移为1右移，循环half>>1，判断node是否空。
特点：使用层数位的二进制可表示某一次的所有节点，位运算确定左右的选择，0左移1右移
class Solution {
public int countNodes(TreeNode root) {
if(root==null)return 0;
TreeNode node = root;
int level=0;
while(node.left!=null){
node=node.left;
level++;
}
int min = 1<0){
if((bits&mid)==0)node=node.left;
else node=node.right;
bits>>=1;
}
return node!=null;
}
}
（4）110. 平衡二叉树
①dfs自下而上，先判断左右子树，并将高度回溯，返回-1进行剪枝
class Solution {
public boolean isBalanced(TreeNode root) {
return getDepth(root)>=0;
}
private int getDepth(TreeNode node){
if(node==null) return 0;
int left = getDepth(node.left);
int right = getDepth(node.right);
if(left==-1||right==-1||Math.abs(left-right)>1)return -1;
return Math.max(left,right)+1;
}
}
②dfs自上而下，先计算根节点再判断左右子树
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null)return true;
return Math.abs(getDepth(root.left)-getDepth(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
}
private int getDepth(TreeNode node){
if(node==null) return 0;
return Math.max(getDepth(node.left),getDepth(node.right))+1;
}
}
（5）257. 二叉树的所有路径
①dfs，递归不空节点和已有路径，为叶子节点时记录结果
class Solution {
private List res;
public List binaryTreePaths(TreeNode root) {
res = new ArrayList<>();
if(root==null)return res;
dfs(root,Integer.toString(root.val));
return res;
}
private void dfs(TreeNode node,String s){
if(node.left==null&&node.right==null)res.add(s);
if(node.left!=null)dfs(node.left,s+"->"+Integer.toString(node.left.val));
if(node.right!=null)dfs(node.right,s+"->"+Integer.toString(node.right.val));
}
}
②bfs+队列，nodeQueue记录节点，pathQueue记录每个节点对应的路径，若为叶子节点则记录结果
class Solution {
private List res;
private Deque nodeQueue;
private Deque pathQueue;
public List binaryTreePaths(TreeNode root) {
res = new ArrayList<>();
if(root==null)return res;
nodeQueue = new ArrayDeque<>();
pathQueue = new ArrayDeque<>();
nodeQueue.addLast(root);
pathQueue.addLast(Integer.toString(root.val));
while(!nodeQueue.isEmpty()){
TreeNode tempNode = nodeQueue.pollFirst();
String tempPath = pathQueue.pollFirst();
if(tempNode.left==null&&tempNode.right==null)res.add(tempPath);
if(tempNode.left!=null){
nodeQueue.addLast(tempNode.left);
pathQueue.addLast(tempPath+"->"+Integer.toString(tempNode.left.val));
}
if(tempNode.right!=null){
nodeQueue.addLast(tempNode.right);
pathQueue.addLast(tempPath+"->"+Integer.toString(tempNode.right.val));
}
}
return res;
}
}
（6）404. 左叶子之和
①bfs+队列，同102题层序遍历（可看上一篇），记录每层第一个节点的和
②dfs，递归并记录是否为左孩子，若为左孩子并为叶子节点，则记录值
class Solution {
private int res;
public int sumOfLeftLeaves(TreeNode root) {
if(root==null)return 0;
res=0;
dfs(root,false);
return res;
}
private void dfs(TreeNode node, boolean isLeft){
if(isLeft&&node.left==null&&node.right==null){
res+=node.val;
return;
}
if(node.left!=null)dfs(node.left,true);
if(node.right!=null)dfs(node.right,false);
}
}
③dfs，有左孩子时判断左孩子是否为叶子节点，极简版
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null)return 0;
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)
+ (root.left!=null&&root.left.left==null&&root.left.right==null ? root.left.val : 0);
}
}
（7）513. 找树左下角的值
①bfs+队列，同102题层序遍历（可见上一篇），记录最新一层第一个节点的值。或者每层从右到左遍历，记录的最后一个节点即为结果
②dfs，递归每个节点的层数，并记录最底层的层数，遇到新层记录结果
class Solution {
private int maxDepth = 0, res = 0;
public int findBottomLeftValue(TreeNode root) {
dfs(root,1);
return res;
}
private void dfs(TreeNode node,int depth){
if(node==null)return;
if(depth>maxDepth){
res = node.val;
maxDepth = depth;
}
dfs(node.left,depth+1);
dfs(node.right,depth+1);
}
}
（8）112. 路径总和
①dfs，同257题，当为叶子节点且路径和满足时返回true
class Solution {
private int target;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)return false;
target = targetSum;
return dfs(root,0);
}
private boolean dfs(TreeNode node,int sum){
if(node==null)return false;
sum+=node.val;
if(node.left==null&&node.right==null&&sum==target)return true;
return dfs(node.left,sum)||dfs(node.right,sum);
}
}
②bfs+队列，同257题，nodeQueue记录节点，sumQueue记录节点对应的和，当取出的节点为叶子并且和为目标，返回true
③dfs，递归targetSum-root.val，若当前节点为叶子节点，则判断节点值是否与递归和相同
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)return false;
if(root.left==null&&root.right==null)return root.val==targetSum;
return hasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);
}
}
二叉树篇Ⅲ总结
①bfs和dfs都可以很方便的遍历二叉树
②对于翻转二叉树、对称二叉树、平衡二叉树这种题，使用dfs非常方便
③dfs分为自下而上（从叶子到根）和自上而下（从根到叶子）两种，按题目需求选择，如110和112题
④对于222题的完全二叉树问题，使用二分法缩短查找时间，使用层数位二进制表示一层集结点，使用位运算确定一条到叶子节点的路径
