算法通过村第8关【青铜】| 二叉树的经典算法题

二叉树的双指针

1.相同的树

思路：递归的挨个比较是否相同

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if((p == null&&q!=null) || (p != null && q == null) || (p!=null&&q!=null&&p.val != q.val)){return false;}if(p == q && p == null){return true;}boolean left = isSameTree(p.left,q.left);boolean right = isSameTree(p.right,q.right);return left&&right;}}

 2.对称二叉树

思路：分别判断左边对称和右边对称即可

class Solution {public boolean isSymmetric(TreeNode root) {return trace(root.left,root.right);}public boolean trace(TreeNode left,TreeNode right) {if(left == null && right!=null){return false;}if(left != null && right==null){return false;}if(left == right){return true;}if(left.val != right.val){return false;}boolean l = trace(left.left,right.right);boolean r = trace(left.right,right.left);return l&&r;}}

 3.合并二叉树

思路：递归三部曲

第一步：确定参数和返回值

显而易见，本题需要同步遍历两颗二叉树，TreeNode trace(TreeNode root1, TreeNode root2)

第二步：确定结束条件

当遇到root2为空或者root1为空就不需要再向下递归找相加了

第三步：确定单层逻辑

当root1和root2不为空，则两值相加

 当root2为空，直接返回root1

当root1为空，直接返回root2

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {return trace(root1,root2);}public TreeNode trace(TreeNode root1, TreeNode root2) {if(root2 == null){return root1;}if(root1 != null && root2!=null){root1.val = root1.val + root2.val;}if(root1 == null && root2!= null){return root2;}root1.left = trace(root1.left,root2.left);root1.right = trace(root1.right,root2.right);return root1;}}

路径专题

1.二叉树的所有路径

思路：

第一步：确定参数和返回值

题目要求从根结点到叶子结点的所有路径，只需要下一个结点和字符串记录 

void trace(TreeNode root,StringBuilder r)

第二步：确定结束条件

也就是什么时候找完一条路径，也就是什么时候找到叶子结点，也就是左右孩子都为空

第三步：确定单层逻辑

保存路径上的结点

class Solution { List<String> res = new LinkedList<>();public List<String> binaryTreePaths(TreeNode root) {String r = "";trace(root,r);return res;}public void trace(TreeNode root,String r){if(root == null){return;}r = r + root.val;     if(root.left == null && root.right == null){res.add(r);return;}r = r+"->";trace(root.left,r);trace(root.right,r);}
}

2.路径总和

思路：递归三部曲

第一步：确定参数和返回值

题目要求找到是否有一条路径符合要求，返回boolean，需要参数记录路径之和还有目标值

boolean hasPathSum(TreeNode root,int res,int targetSum)

 第二步：确定终止条件

当找到一条路径就结束

第三步：确定单层逻辑

当前路径求和

class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {int res = 0;return hasPathSum(root,res,targetSum);}public boolean hasPathSum(TreeNode root,int res,int targetSum){if(root == null){return false;}res += root.val;if(root.left == null && root.right == null){if(res == targetSum){return true;}return false;}boolean left = hasPathSum(root.left,res,targetSum);boolean right = hasPathSum(root.right,res,targetSum);return left || right;}
}

翻转

思路：递归三部曲

第一步： 确定参数和返回值

翻转二叉树需要两两交换左右结点，遍历每一个结点进行交换即可。即参数root返回void

第二步：确定结束条件

结点为空

第三步：确定单层逻辑

每一个结点交换左右子树

class Solution {public TreeNode invertTree(TreeNode root) {trace(root);return root;}public void trace(TreeNode root){if(root == null){return;}TreeNode t = root.left;root.left = root.right;root.right = t;trace(root.left);trace(root.right);}
}