树专题_牛客博客

1. 验证是不是二叉搜索树

https://leetcode-cn.com/problems/validate-binary-search-tree/submissions/

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. 中序遍历非递归

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

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. 前中得树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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. 两个节点的最低公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

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. 树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/

每次到一个节点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. 树最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/submissions/

每次到一个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. 二叉搜索树迭代器

https://leetcode-cn.com/problems/binary-search-tree-iterator/

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 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. 序列化二叉树

https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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;
    }
}