java面试题网

普通会员

217

帖子

75

回复

160

积分

楼主
发表于 2019-05-06 15:10:23 | 查看: 5259| 回复: 0

java二叉树算法面试题大全含答案

java二叉树算法面试题大全含答案
1.给定一颗二叉树,返回节点值得先序遍历,请使用迭代(非递归)方式实现。
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if(root == null)
return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
return result;
}
}

2.验证一棵树是否为有效的二叉搜索树BST
public class Solution {
private static int lastVisit = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
boolean judgeLeft = isValidBST(root.left); // 先判断左子树

if(root.data >= lastVisit && judgeLeft) { // 当前节点比上次访问的数值要大
lastVisit = root.data;
} else {
return false;
}
boolean judgeRight = isValidBST(root.right); // 后判断右子树
return judgeRight;
}
}

3.二叉搜索树BST中第Kth小的元素 题目:给定⼀个BST,写一个函数kthSmallest来找到第kth小的元素
public class Solution2 {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> store = new Stack<TreeNode>();
if (root == null) {
return -1;
}
store.push(root);
while (root.left != null) {
store.push(root.left);
root = root.left;
}
while (!store.empty()) {
TreeNode cur = store.pop();
k--;
if (k == 0) {
return cur.val;
}
if (cur.right != null) {
root = cur.right;// let cur.right be the current node
store.push(root);
while (root.left != null) {
store.push(root.left);
root = root.left;
}
}
}
return -1;
}
}

4.迭代方法实现二叉树的先序遍历:题目: 给定一颗⼆叉树,返回节点值得先序遍历,请使用迭代(非递归)方式实现。

比如, 给定二叉树{1,#,2,3}, 返回 [1,2,3]
public class Solution {
List<Integer> result = new ArrayList<Integer>();
/**
* 迭代实现,维护一个栈,因为入栈顺序按照根右左进行入栈,因此首先将根出栈,然后出栈左子节点,
* 最后出栈右子节点。
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null)
return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
return result;
}
}

5.验证二叉搜索树BST:题目: 验证一棵树是否为有效的二叉搜索树BST比如,二叉树[2, 1, 3],返回true二叉树[1, 2, 3], 返回false
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BSTChecker {
private static int lastVisit = Integer.MIN_VALUE;

public static boolean isBST(TreeNode root) {
if(root == null) return true;

boolean judgeLeft = isBST(root.left); // 先判断左子树

if(root.val >= lastVisit && judgeLeft) { // 当前节点比上次访问的数值要大
lastVisit = root.val;
} else {
return false;
}
boolean judgeRight = isBST(root.right); // 后判断右子树
return judgeRight;
}
}



文章来自www.wityx.com,转载请注明出处!原文地址http://www.wityx.com/post/806_1_1.html

您需要登录后才可以回帖 登录 | 立即注册

java面试题网www.wuliaokankan.cnjava建站系统提供技术支持V2.1 网站地图 © 2016-2018