当前位置：首页 > news >正文

刷算法Leetcode---9（二叉树篇Ⅲ）

news 来源：原创 2024/9/20 17:35:47

前言

本文是跟着代码随想录的二叉树顺序进行刷题并编写的代码随想录

二叉树的题目较多，就多分了几次写，这是第三篇

这是力扣刷算法的其他文章链接：刷算法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<TreeNode> queue;public boolean isSymmetric(TreeNode root) {if(root == null) return true;queue = new LinkedList<TreeNode>();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<<level, max = (1<<(level+1))-1;while(min<max){int mid = (max-min+1)/2+min;if(exist(root,level,mid)) min = mid;else max=mid-1;}return min;}private boolean exist(TreeNode root,int level,int mid){int bits = 1<<(level-1);TreeNode node = root;while(node!=null&&bits>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<String> res;public List<String> 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<String> res;private Deque<TreeNode> nodeQueue;private Deque<String> pathQueue;public List<String> 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);}
}