网站建设和服务器运营,专业的佛山网站建设公司,怎样建设网站是什么样的,番禺网站建设培训2024.2.19 题目来源我的题解方法一 递归实现#xff08;深度优先遍历#xff09;方法二 迭代实现#xff08;栈#xff09; 题目来源
力扣每日一题#xff1b;题序#xff1a;590
我的题解
方法一 递归实现#xff08;深度优先遍历#xff09; 与二叉树的后序遍历的… 2024.2.19 题目来源我的题解方法一 递归实现深度优先遍历方法二 迭代实现栈 题目来源
力扣每日一题题序590
我的题解
方法一 递归实现深度优先遍历 与二叉树的后序遍历的递归实现相似只是有些细节不一样 时间复杂度O(n) 空间复杂度O(n) public ListInteger postorder(Node root) {ListInteger resnew ArrayList();if(rootnull)return res;post(root,res);return res;
}
public void post(Node root,ListInteger res){if(rootnull)return ;// 细节的不同for(Node node:root.children){post(node,res);}res.add(root.val);
}方法二 迭代实现栈 与二叉树的后序遍历的迭代实现相似但是细节处不相同 时间复杂度O(n) 空间复杂度O(n) public ListInteger postorder(Node root) {ListInteger resnew ArrayList();if(rootnull)return res;LinkedListNode stacknew LinkedList();stack.push(root);Node prenull;while(!stack.isEmpty()){Node curstack.peek();System.out.println(cur.children.size());//判断是否遍历完当前节点的所有子节点boolean ffalse;for(Node node:cur.children){f|nodepre;}//判断当前节点是否是叶子节点有所不同if(cur.children.size()0||((pre!null)f)){Node tstack.pop();res.add(t.val);pret;}else{//从右往左压栈for(int icur.children.size()-1;i0;i--){Node nodecur.children.get(i);stack.push(node);}}}return res;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
