西安商城网站建设咪豆,com域名表示的是什么机构,手机端网站如何做,php综合网站建设论文【问题描述】199.二叉树的右视图
给定一棵二叉树#xff0c;想象自己站在它的右侧#xff0c;按照从顶部到底部的顺序#xff0c;返回从右侧所能看到的节点值。示例:输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:1 ---/ \
2 3 ---\…【问题描述】199.二叉树的右视图
给定一棵二叉树想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。示例:输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:1 ---/ \
2 3 ---\ \5 4 ---【解答思路】
1. BFS
层次遍历时保存每层的最右一个节点 时间复杂度O(N) 空间复杂度O(N)
public ListInteger rightSideView(TreeNode root) {if(root null){return new ArrayList();}ListInteger ret new ArrayList();QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty() ){每层的sizeint size queue.size();//遍历当层for(int i 0; isize ;i){TreeNode node queue.poll();//最右边 if(size-1 i ){ret.add(node.val);}//遍历当层节点添加下一层节点if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}}}return ret;}2. 前序遍历改造先访问右子树
时间复杂度O(N) 空间复杂度O(N) public ListInteger rightSideView(TreeNode root) {ListInteger res new ArrayList();dfs(root, 0, res);return res;}private void dfs(TreeNode node, int level, ListInteger res) {if (node null)return;if (level res.size()) res.add(node.val); // 每一层的第一个节点dfs(node.right, level1, res);dfs(node.left, level1, res);}
【总结】
1.二叉树遍历
前序遍历 先输出当前结点的数据再依次遍历输出左结点和右结点中序遍历 先遍历输出左结点再输出当前结点的数据再遍历输出右结点后续遍历 先遍历输出左结点再遍历输出右结点最后输出当前结点的数据
2. Queue操作 3. 切割子问题 分层思考
