【基础算法精讲 10】如何灵活运用递归？

100. 相同的树给你两棵二叉树的根节点p和q编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){//边界值当前节点为空时则返回falseif(pnull||qnull){returnpq;//都为null则返回true}//相同的树当前节点的值相等且左子树相等右子树相等。returnp.valq.valisSameTree(p.left,q.left)isSameTree(p.right,q.right);}}101. 对称二叉树给你一个二叉树的根节点root 检查它是否轴对称。思路在相同的树这段代码上改判断左子树的左孩子是否等于右子树的右孩子左子树的右孩子是否等于右子树的左孩子 代码classSolution{publicbooleanisSameTree(TreeNodep,TreeNodeq){if(pnull||qnull){returnpq;}returnp.valq.valisSameTree(p.left,q.right)isSameTree(p.right,q.left);}publicbooleanisSymmetric(TreeNoderoot){//可以在相同的树代码逻辑上改//看左子树的左孩子是否等于右子树的右孩子左子树的右孩子是否等于左子树的右孩子returnisSameTree(root.left,root.right);}}110. 平衡二叉树给定一个二叉树判断它是否是平衡二叉树思路 用-1表示该树不是平衡二叉树如果该树中某一个节点不是平衡节点就立马返回-1一直返回到调用入口表示该树为非平衡二叉树。 代码classSolution{//获得子树高度publicintgetDepth(TreeNodenode){if(nodenull){return0;}//获取左子树高度intleft_heightgetDepth(node.left);if(left_height-1){return-1;}//获取右子树高度intright_heightgetDepth(node.right);if(right_height-1||Math.abs(left_height-right_height)1){return-1;}returnMath.max(left_height,right_height)1;}publicbooleanisBalanced(TreeNoderoot){//用-1记录该树为非平衡二叉树returngetDepth(root)!-1;}}199. 二叉树的右视图给定一个二叉树的根节点root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例 1输入root [1,2,3,null,5,null,4]输出[1,3,4]解释思路1、用一个全局数组ans,初始值为空。2、先遍历右子树比较当前树的深度是否大于数组长度若大于则表示该节点是被第一次看见需要记录到答案数组中。3、必须先遍历右子树再遍历左子树 代码classSolution{ListIntegeransnewArrayList();publicvoiddepth(TreeNodenode,intdepth){if(nodenull){return;}depth1;if(depthans.size()){ans.add(node.val);}//必须先遍历右子树depth(node.right,depth);depth(node.left,depth);}publicListIntegerrightSideView(TreeNoderoot){//先遍历右子树//若答案的长度小于当前树的深度时证明该节点是第一个能看到的结点要把该节点记录到答案中。depth(root,0);returnans;}}