树专题
1. 验证是不是二叉搜索树
class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
Stack<TreeNode> s = new Stack<TreeNode>();
long pre = Long.MIN_VALUE;
while(root != null || !s.isEmpty()){
while(root != null){
s.push(root);
root = root.left;
}
TreeNode tmp = s.pop();
if (tmp.val <= pre)
return false;
pre = tmp.val;
root = tmp.right;
}
return true;
}
}
//递归：传入大小范围：
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
return dfs(root,Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean dfs(TreeNode root, long min, long max){
if (root == null)
return true;
if (root.val <= min || root.val >= max)
return false;
return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
}
}
2. 中序遍历非递归
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while(p != null || !stack.isEmpty()){
while(p != null){
stack.push(p);
p = p.left;
}
p = stack.pop();
res.add(p.val);
p = p.right;
}
return res;
}
}
3. 前中得树
class Solution {
private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null|| inorder == null || preorder.length != inorder.length)
return null;
for(int i = 0; i < preorder.length; i++)
map.put(inorder[i], i);
int n = preorder.length;
return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}
private TreeNode dfs(int[] pre, int[] in, int l1, int r1, int l2, int r2){
if (l1 > r1)
return null;
int len = map.get(pre[l1]) - l1;
TreeNode root = new TreeNode(pre[l1]);
root.left = dfs(pre, in, l1 + 1, l1 + len, l2, l2 + len -1);
root.right = dfs(pre, in, l1 + len + 1, r1, l2 + len, r2);
return root;
}
}
4. 两个节点的最低公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return root;
if (root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null)
return root;
else if (left != null)
return left;
else if (right != null)
return right;
return null;
}
}
5. 树的直径
每次到一个节点root时候，做两件事：
1. 更新当前的最大值（左加右）
2. 左右中更大的为当前root的边值，再加一。
class Solution {
private int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode root){
if (root == null)
return 0;
int l = dfs(root.left);
int r = dfs(root.right);
res = Math.max(res, l + r);
return Math.max(l,r) + 1;
}
}
6. 树最大路径和
每次到一个root，做两件事：
1. 三点之和更新res
2. 左右中大的，加上root为当前（只能往一条走）
class Solution { private int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode root){
if (root == null)
return 0;
int left = Math.max(0, dfs(root.left)); //遇到负值， 不下去了
int right = Math.max(0,dfs(root.right));
res = Math.max(res, left + right + root.val);
return Math.max(left, right) + root.val;
}
} 7. 二叉搜索树迭代器
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
class BSTIterator {
private Stack<TreeNode> s = new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
TreeNode p = root;
while(p != null){
s.push(p);
p = p.left;
}
}
/** @return the next smallest number */
public int next() {
TreeNode cur = s.pop();
int res = cur.val;
cur = cur.right;
while(cur != null){
s.push(cur);
cur = cur.left;
}
return res;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !s.isEmpty();
}
}
8. 先序后序遍历非递归
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null)
return res;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while(!s.isEmpty()){
TreeNode tmp = s.pop();
res.add(tmp.val);
if (tmp.right != null)
s.push(tmp.right);
if (tmp.left != null)
s.push(tmp.left);
}
return res;
}
} class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null)
return res;
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
TreeNode p = root;
s1.push(p);
while(!s1.isEmpty()){
TreeNode tmp = s1.pop();
s2.push(tmp);
if (tmp.left != null)
s1.push(tmp.left);
if (tmp.right != null)
s1.push(tmp.right);
}
while(!s2.isEmpty())
res.add(s2.pop().val);
return res;
}
} 9. 序列化二叉树
public class Solution {
String Serialize(TreeNode root) {
if (root == null)
return "#";
return String.valueOf(root.val) + " " + Serialize(root.left) + " " + Serialize(root.right);
}
private String dstr;
TreeNode Deserialize(String str) {
dstr = str;
return Deserialize();
}
private TreeNode Deserialize(){
if (dstr.length() == 0)
return null;
int index = dstr.indexOf(" ");
String node = index == -1 ? dstr:dstr.substring(0, index); //截取节点
dstr = index == -1 ? "":dstr.substring(index + 1); //更新剩下的
if (node.equals("#"))
return null; //若为空
TreeNode t = new TreeNode(Integer.valueOf(node));
t.left = Deserialize();
t.right = Deserialize();
return t;
}
}
投递完美世界等公司6个岗位 >
