群晖可以做网站服务器吗,可以做哪些有趣的网站,wordpress 注册邮箱验证失败,微信网页制作的软件用了递归遍历#xff0c;关于树的经典例题。
题目 递归
常规做法即递归了#xff0c;不会写也得背下来。递归可以大致理解方法调用自身#xff0c;先写中序遍历递归的方法#xff0c;递归一定要有递归出口#xff0c;当遍历到节点为空时返回#xff0c;即已经找到了。…用了递归遍历关于树的经典例题。
题目 递归
常规做法即递归了不会写也得背下来。递归可以大致理解方法调用自身先写中序遍历递归的方法递归一定要有递归出口当遍历到节点为空时返回即已经找到了。可以看一下为什么是这三行中序遍历为左中右顺序那就可以先从根节点一直往左边找直到找到最左边的节点这是“递”然后到了这个节点时第一个inorder就会return即开始“归”了返回上一个inorder是不是就是该节点了直接下一步add将当前节点值加进list集然后下一个inorder就是遍历右边的节点了当然这时右边有节点也会一直遍历下去然后这里的顺序还是符合中序遍历因为每次执行add时都是把当前节点为根节点这样递归反复在当前节点的左节点会在上一步返回先在当前节点的右节点也会在该节点进入list集后在下一步返回。然后在另一个方法引入返回list集即可。
时间复杂度O(n)空间复杂度O(n)。
/*** 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;* }* }*/
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();inorder(root, res);return res;}public void inorder(TreeNode root, ListInteger res) {if (root null) {return;}inorder(root.left, res);res.add(root.val);inorder(root.right, res);}
}循环
那要是不用递归怎么写上述其实也可以看作是一个模拟栈递归的时候隐式地维护了一个栈而我们在迭代的时候需要显式地将这个栈模拟出来用循环能让这个栈更明显。先用外循环看看这个栈是否为空节点非空也即要遍历的节点然后下一个节点又是节点非空把当前节点压入栈指针左移不断找左节点入栈直到节点空了即找不到了该循环结束然后就开始出栈。出栈时位于栈顶的元素先出即最左的元素先出加进结果集后指针右移继续寻找右边的节点看看能否进行出栈然后如此反复就又是一个中序遍历了思路是跟递归是差不多的。不想写多一个whlie就把while改为if然后后面几行用else括住也能达到类似的效果。
时间复杂度O(n)空间复杂度O(n)。
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();DequeTreeNode stk new LinkedListTreeNode();while (root ! null || !stk.isEmpty()) {while (root ! null) {stk.push(root);root root.left;}//一直往左找root stk.pop();res.add(root.val);root root.right;//指针右移}return res;}
}
Morris 中序遍历
不使用任何辅助空间用上前驱节点省去了栈的空间复杂度。先把根节点及根节点的右节点部分看成一大块连到根节点的左节点部分的最右节点上然后以这样的方式反复拆分左节点就会在前面先遍历像链表一样的顺序不过改变了整个树的结构。
时间复杂度O(n)空间复杂度O(1)。
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();TreeNode pre null;while(root!null) {//如果左节点不为空就将当前节点连带右子树全部挂到//左节点的最右子树下面if(root.left!null) {pre root.left;while(pre.right!null) {pre pre.right;}pre.right root;//将root指向root的leftTreeNode tmp root;root root.left;tmp.left null;//左子树为空则打印这个节点并向右边遍历 } else {res.add(root.val);root root.right;}}return res;}
}
当不想改变树的结构时也可以进行链表的模拟当遍历完后将前驱节点的指针恢复即可。
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();TreeNode pre null;while (root ! null) {if (root.left ! null) {// pre 节点就是当前 root 节点向左走一步然后一直向右走至无法走为止pre root.left;while (pre.right ! null pre.right ! root) {pre pre.right;}// 让 pre 的右指针指向 root继续遍历左子树if (pre.right null) {pre.right root;root root.left;}// 说明左子树已经访问完了我们需要断开链接else {res.add(root.val);pre.right null;root root.right;}}// 如果没有左孩子则直接访问右孩子else {res.add(root.val);root root.right;}}return res;}
}像树这种结构很适合用递归循环实现。
