【面试】算法题之二叉树右视图（并构建二叉树）
本帖最后由 落神 于 2021-1-12 17:13 编辑看见很多大佬分享了一些算法，最近自己也在准备找实习，也来发一发。
构建二叉树：迭代
右视图：BFS+队列
import java.util.*;
class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* xianxu int整型一维数组 先序遍历
* zhongxu int整型一维数组 中序遍历
* int整型一维数组
*/
public int[] solve (int[] xianxu, int[] zhongxu) {
// write code here
if(xianxu.length == 0 || zhongxu.length == 0)
return null;
//构建二叉树
TreeNode root = buildTree(xianxu,zhongxu);
//右视图层次遍历 只保存最后一个节点
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
if(i == size-1)
list.add(node.val);
if(node.left != null)
queue.add(node.left);
if(node.right != null)
queue.add(node.right);
}
}
int[] result = new int;
for(int i=0;i<list.size();i++)
result = list.get(i);
return result;
}
public TreeNode buildTree(int[] xianxu, int[] zhongxu){
//双指针
int pre = 0;
int mid = 0;
//当前节点
TreeNode curRoot = new TreeNode(xianxu);
//root作为根节点 返回
TreeNode root = curRoot;
Stack<TreeNode> stack = new Stack<>();
//入栈
stack.push(curRoot);
pre++;
while(pre < xianxu.length){
//当前节点 = 中序遍历的节点时候，证明下一个节点是右子树的节点
if(curRoot.val == zhongxu){
//出栈 与中序遍历匹配 不匹配时证明先序遍历的值是当前节点的右节点
while(!stack.isEmpty() && stack.peek().val == zhongxu){
curRoot = stack.pop();
//mid同步，更新到下一个右节点判断
mid++;
}
//设置右节点
curRoot.right = new TreeNode(xianxu);
//更新节点
curRoot = curRoot.right;
//入栈
stack.push(curRoot);
pre++;
}else{
//设置左节点
curRoot.left = new TreeNode(xianxu);
curRoot = curRoot.left;
stack.push(curRoot);
pre++;
}
}
return root;
}
} 学习了，感谢帖主分享
页:
[1]