淄博网站制作网络定制,好的设计公司网站,宁波网站推广哪家公司好,网上互联网推广文章目录 题目方法一#xff1a;单循环栈做法方法二#xff1a;递归 题目 方法一#xff1a;单循环栈做法
关键在于子节点的入栈顺序#xff0c;决定了子节点的出栈顺序#xff0c; 因为是前序遍历 所以压栈顺序先让右边的入栈 依次往左 这样左边的节点会在栈顶 这样下次… 文章目录 题目方法一单循环栈做法方法二递归 题目 方法一单循环栈做法
关键在于子节点的入栈顺序决定了子节点的出栈顺序 因为是前序遍历 所以压栈顺序先让右边的入栈 依次往左 这样左边的节点会在栈顶 这样下次优先出栈的是左边的元素 满足前序遍历 for(int i root.children.size()-1 ; i0 ;i--)stack.push(root.children.get(i));class Solution {public ListInteger preorder(Node root) {if(rootnull) return new ArrayList();ListInteger res new ArrayList();DequeNode stack new LinkedList();stack.push(root);while(!stack.isEmpty()){root stack.pop();res.add(root.val);//因为是前序遍历 所以压栈顺序先让右边的入栈 依次往左 这样左边的节点会在栈顶 这样下次优先出栈的是左边的元素 满足前序遍历for(int i root.children.size()-1 ; i0 ;i--)stack.push(root.children.get(i));}return res;}
}方法二递归
原理和二叉树的前序遍历一样 相当于把左右孩子 改成孩子集合了 孩子变多了而已核心还是 根左右先跟 再左孩子 在右孩子
class Solution {ListInteger res new ArrayList();public ListInteger preorder(Node root) {dfs(root);return res;}public void dfs(Node root){if(root null) return;res.add(root.val);//前for(Node node : root.children)//中中中中中dfs(node);}
}
