网站开发程序用什么好,中国第八冶金建设公司网站,最新网站建设,东营赶集网文章目录 6.翻转二叉树6.1问题6.2解法一#xff1a;递归6.2.1递归思路#xff08;1#xff09;确定递归函数的参数和返回值#xff08;2#xff09;确定终止条件#xff08;3#xff09;确定单层递归的逻辑 6.2.2全部代码 6.3解法二#xff1a;层序遍历 7.对称二叉树7.… 文章目录 6.翻转二叉树6.1问题6.2解法一递归6.2.1递归思路1确定递归函数的参数和返回值2确定终止条件3确定单层递归的逻辑 6.2.2全部代码 6.3解法二层序遍历 7.对称二叉树7.1问题7.2解法一递归7.2.1递归思路1确定递归函数的参数和返回值2确定终止条件3确定单层递归的逻辑 7.2.2代码实现 7.3解法二迭代法 8.完全二叉树的节点个数8.1问题8.2解法一递归8.3解法二层序遍历 9.平衡二叉树9.1问题9.2解法一递归9.2.1递归思路1确定递归函数返回值和参数值2确定终止条件3确定递归逻辑 9.2.2代码 10.完全二叉树的所有路径10.1问题10.2解法一前序遍历回溯10.2.1递归思路1确定递归函数参数以及返回值2确定递归终止条件3确定递归逻辑 10.2.2代码实现 6.翻转二叉树
6.1问题
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
示例一 输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]6.2解法一递归
6.2.1递归思路
1确定递归函数的参数和返回值
题目为翻转根节点的左右孩子最后返回根节点即每次递归传入TreeNode节点返回该节点
TreeNode reverse(TreeNode node);2确定终止条件
当递归到的该节点为空即返回
if(nodenull){return;
}3确定单层递归的逻辑
当确定该节点不为空先交换左、右孩子再分别递归左孩子、右孩子
swap(node);
reverse(node.left);
reverse(node.right);6.2.2全部代码
class Solution {public TreeNode invertTree(TreeNode root) {if(rootnull){return root;}return reverse(root);}private TreeNode reverse(TreeNode node){if(nodenull){return node;}swap(node);reverse(node.left);reverse(node.right);return node;}private void swap(TreeNode node){TreeNode tmpnode.left;node.leftnode.right;node.righttmp;}
}6.3解法二层序遍历
将每一个从队列取出来的元素进行左孩子和有孩子的交换
class Solution {public TreeNode invertTree(TreeNode root) {//广度优先遍历QueueTreeNode queuenew LinkedList();if(rootnull){return root;}queue.offer(root);while(!queue.isEmpty()){int sizequeue.size();while(size0){TreeNode nodequeue.poll();swap(node);if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}size--;}}return root;}private void swap(TreeNode node){TreeNode tmpnode.left;node.leftnode.right;node.righttmp;}
}7.对称二叉树
7.1问题
给你一个二叉树的根节点 root 检查它是否轴对称。
示例一 输入root [1,2,2,3,4,4,3]
输出true7.2解法一递归
7.2.1递归思路
1确定递归函数的参数和返回值
比较的是根节点的两个子树是否是相互翻转的进而判断这个树是不是对称树所以要比较的是两个树参数自然也是左子树节点和右子树节点。返回值为boolean类型
boolean compare(TreeNode left,TreeNode right)2确定终止条件
首先排除左孩子、右孩子节点有空的情况 左孩子为空右孩子不为空return false左孩子不为空右孩子为空return false左、右孩子均为空return true 左、右孩子均不为空 比较左右孩子的数值不相同return false
if (left NULL right ! NULL) return false;
else if (left ! NULL right NULL) return false;
else if (left NULL right NULL) return true;
else if (left-val ! right-val) return false; // 注意这里我没有使用else3确定单层递归的逻辑
单层递归的逻辑就是处理左右节点都不为空且数值相同的情况。 比较二叉树外侧是否对称传入的是左节点的左孩子右节点的右孩子。比较内侧是否对称传入左节点的右孩子右节点的左孩子。如果左右都对称就返回true 有一侧不对称就返回false 。
boolean outside compare(left.left, right.right); // 左子树左、 右子树右
boolean inside compare(left.right, right.left); // 左子树右、 右子树左
boolean isSame outside inside; // 左子树中、 右子树中逻辑处理
return isSame;7.2.2代码实现
class Solution {public boolean isSymmetric(TreeNode root) {if(rootnull){return true;}return compare(root.left,root.right);}private boolean compare(TreeNode left,TreeNode right){if(leftnull right!null){return false;}else if(left!null rightnull){return false;}else if(leftnull rightnull){return true;}else if(left.val!right.val){return false;}//单层递归逻辑boolean outcompare(left.left,right.right);boolean incompare(left.right,right.left);return (outin);}
}7.3解法二迭代法
使用队列来比较两个树根节点的左右子树是否相互翻转注意这不是层序遍历 class Solution {public boolean isSymmetric(TreeNode root) {//迭代法if(rootnull){return true;}QueueTreeNode queuenew LinkedList();//添加根节点的左右孩子queue.offer(root.left);queue.offer(root.right);while(!queue.isEmpty()){TreeNode leftqueue.poll();TreeNode rightqueue.poll();//1、判断两个节点是否均为空if(leftnull rightnull){continue; //对称结束此次循环再次取出新的两个节点判断}//2、判断不符合对称条件if(leftnull || rightnull || (left.val!right.val)){return false;}//3、添加新的两个节点外层内层queue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;}}8.完全二叉树的节点个数
8.1问题
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2h 个节点。
示例一 输入root [1,2,3,4,5,6]
输出68.2解法一递归
class Solution {public int countNodes(TreeNode root) {return count(root);}private int count(TreeNode node){if(nodenull){return 0;}int leftCountcount(node.left);int rightCountcount(node.right);return leftCountrightCount1;}
}8.3解法二层序遍历
class Solution {public int countNodes(TreeNode root) {//广度优先遍历QueueTreeNode queuenew LinkedList();int count0;if(rootnull){return count;}queue.offer(root);while(!queue.isEmpty()){int sizequeue.size();countsize;while(size0){TreeNode nodequeue.poll();if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}size--;}}return count;}}9.平衡二叉树
9.1问题
给定一个二叉树判断它是否是 平衡二叉树
示例一 输入root [3,9,20,null,null,15,7]
输出true9.2解法一递归
9.2.1递归思路
1确定递归函数返回值和参数值
题目为确定一棵树是否为平衡树平衡树的定义一棵树为空或者其左右节点的高度差的绝对值不超过1即递归函数参数为一个树节点返回值为该节点的高度注意若返回-1则表明该树不平衡
int isBalancedTree(TreeNode node)2确定终止条件
若该节点为null返回0
if(nodenull){return 0;
}3确定递归逻辑
传入一个节点要求返回其高度即需要求其左、右节点的高度分别求完左、右节点的高度之后判断其中是否为-1若为-1则返回-1代表不平衡若均不为-1则求出该节点的平衡因子若其绝对值超过1则返回-1代表不平衡否则返回当前节点为根节点的树的最大高度
int leftHeightisBalancedTree(node.left);
int rightHeightisBalancedTree(node.right);
if(leftHeight-1 || rightHeight-1){return -1;
}
if(Math.abs(leftHeight-rightHeight)1){return -1;
}
return 1Math(leftHeight,rightHeight);9.2.2代码
class Solution {public boolean isBalanced(TreeNode root) {return isBalancedTree(root)!-1;}private int isBalancedTree(TreeNode node){if(nodenull){return 0;}int leftHeightisBalancedTree(node.left);int rightHeightisBalancedTree(node.right);if(leftHeight-1 || rightHeight-1){return -1;}if(Math.abs(leftHeight-rightHeight)1){return -1;}return 1Math.max(leftHeight,rightHeight);}
}10.完全二叉树的所有路径
10.1问题
给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例一 输入root [1,2,3,null,5]
输出[1-2-5,1-3]10.2解法一前序遍历回溯
题目要求从根节点到叶子的路径所以需要前序遍历这样才方便让父节点指向孩子节点找到对应的路径把路径记录下来需要回溯来回退一个路径再进入另一个路径。 10.2.1递归思路
1确定递归函数参数以及返回值
求以node为根节点到达叶子节点的路径paths存放路径值res存放最终结果
void traversal(TreeNode node,ListInteger paths,ListString res)2确定递归终止条件
当遍历到了叶子节点即为一条完整的路径取出paths的全部节点并加入到res中直接return
if(node.leftnull node.rightnull){// 输出StringBuilder sb new StringBuilder();// StringBuilder用来拼接字符串速度更快for (int i 0; i paths.size() - 1; i) {sb.append(paths.get(i)).append(-);}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;
}3确定递归逻辑 // 递归和回溯是同时进行所以要放在同一个花括号里if (root.left ! null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right ! null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}10.2.2代码实现
class Solution {public ListString binaryTreePaths(TreeNode root) {ListInteger pathsnew ArrayList();ListString resnew ArrayList();traversal(root,paths,res);return res;}private void traversal(TreeNode node,ListInteger paths,ListString res){//1、前序遍历中左右处理该节点paths.add(node.val);//2、终止条件该节点为叶子节点if(node.leftnull node.rightnull){StringBuilder sbnew StringBuilder();for(int i0;ipaths.size()-1;i){sb.append(paths.get(i)).append(-);}//加入最后一个节点sb.append(paths.get(paths.size()-1));res.add(sb.toString());return;}//3、递归逻辑回溯if(node.left!null){traversal(node.left,paths,res);//回溯paths.remove(paths.size() - 1); //去除最后一个节点}if(node.right!null){traversal(node.right,paths,res);//回溯paths.remove(paths.size() - 1); //去除最后一个节点}}
}
