树专题 - 《leetcode刷题》

lc98. Validate Binary Search Tree 03:23
lc94. Binary Tree Inorder Traversal 14:34
lc101. Symmetric Tree 26:11
lc105. Construct Binary Tree from Preorder and Inorder Traversal 40:49
lc102. Binary Tree Level Order Traversal 49:45
lc236. Lowest Common Ancestor of a Binary Tree 57:15
lc543. Diameter of Binary Tree 69:16
lc124. Binary Tree Maximum Path Sum 79:52
lc173. Binary Search Tree Iterator 90:53
lc297. Serialize and Deserialize Binary Tree 97:34
视频地址：https://www.bilibili.com/video/BV19t411w7Ep

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:
输入:
2
/ \
1 3
输出: true

示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
方法一：递归

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);
        //这里用long用来判断边界情况，根节点的值可能等于int类型的max
    }
    public boolean dfs(TreeNode node,long lower,long upper){
        if(node==null)
            return true;
        if(node.val<=lower||node.val>=upper) return false;
        //这里等于也不满足定义，下面也不用减一判断，保证测试用例给的在int范围，递归时候也在int范围
        return dfs(node.left,lower,node.val)&&dfs(node.right,node.val,upper);
        //递归左子树，值要小于在node的值，右子树要大于node的值，又要在上下界内。
    }
}

方法二：用中序遍历有序的方法
1.用非递归

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack =new LinkedList<TreeNode>();
        TreeNode p=root;
        double pre=-Double.MAX_VALUE;
        while(p!=null||!stack.isEmpty()){
            while(p!=null){
                stack.push(p);
                p=p.left;
            }
            p=stack.pop();
            if(p.val<=pre){
                return false;
            }else
            pre=p.val;
            p=p.right;
        }
        return true;
    }

2.用递归

class Solution {
    double pre=-Double.MAX_VALUE;
    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }
    public boolean inorder(TreeNode node){
        if(node==null)
        return true;
        if(inorder(node.left)==false) return false;//要加判断
        if(node.val<=pre)
            return false;
        else
        pre=node.val;
        return inorder(node.right);    
    }
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

示例 1：
树专题 - 图1
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
树专题 - 图2
输入：root = [1,2]
输出：[2,1]

示例 5：
树专题 - 图3
输入：root = [1,null,2]
输出：[1,2]
解法一：用栈的非递归版本

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack =new LinkedList<TreeNode>();
        List<Integer> res=new ArrayList<Integer>();
        TreeNode p=root;
        while(p!=null||!stack.isEmpty()){//栈不空且p不空
            while(p!=null){
                stack.push(p);
                p=p.left;//左边全部入栈
            }
            p=stack.pop();//取栈顶，看有没有右子树，有的话，再左边入栈
            res.add(p.val);
            p=p.right;
        }
        return res;
    }
}

解法二：递归版本

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        inorder(root,res);
        return res;
    }
    public void inorder(TreeNode node,List<Integer> list){
        if(node==null)
        return;
        inorder(node.left,list);
        list.add(node.val);
        inorder(node.right,list);
    }
}

101. 对称二叉树

难度简单1221
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3

递归的方法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return dfs(root.left,root.right);
    }
    public boolean dfs(TreeNode p,TreeNode q){
        if(p==null||q==null) return p==null&&q==null;//两个同时为空返回true
        return p.val==q.val&&dfs(p.left,q.right)&&dfs(p.right,q.left);
    }
}

非递归的方法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        Deque<TreeNode> left=new LinkedList<TreeNode>();
        Deque<TreeNode> right=new LinkedList<TreeNode>();
        TreeNode l=root.left,r=root.right;
        while(l!=null||r!=null||!left.isEmpty()||!right.isEmpty()){
            while(l!=null&&r!=null){
                left.push(l); l=l.left;
                right.push(r); r=r.right;
            }
            if(l!=null||r!=null) return false;
            l=left.pop();
            r=right.pop();
            if(l.val!=r.val)
                return false;
            l=l.right;
            r=r.left;
        }
        return true;
    }
}

105. 从前序与中序遍历序列构造二叉树

难度中等848
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7

class Solution {
    HashMap<Integer,Integer> pos=new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n=preorder.length;
        for(int i=0;i<n;i++) pos.put(inorder[i],i);
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }
    public TreeNode dfs(int[] preorder,int[] inorder,int pl,int pr,int il,int ir){
        if(pl>pr) return null;
        int val =preorder[pl];
        int k=pos.get(val);
        int len=k-il;
        TreeNode root=new TreeNode(val);
        root.left=dfs(preorder,inorder,pl+1,pl+len,il,k-1);
        root.right=dfs(preorder,inorder,pl+len+1,pr,k+1,ir);
        return root;
    }
}

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7

返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root==null) return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len =queue.size();
            List<Integer> level=new ArrayList<Integer>();
            for(int i=0;i<len;i++){
                TreeNode t=queue.poll();//检索并删除此列表的头部（第一个元素）
                level.add(t.val);
                if(t.left!=null) queue.offer(t.left);
                if(t.right!=null) queue.offer(t.right);
            }
            res.add(level);
        }
        return res;
    }
}

236. 二叉树的最近公共祖先

难度中等922收藏分享切换为英文接收动态反馈
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
树专题 - 图6

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5和节点 1的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5和节点 4的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||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 null;
        if(Left==null) return Right;
        if(Right==null) return Left;
        return root;

    }
}

543. 二叉树的直径

难度简单603
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树
1
/ \
2 3
/ \
4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans=1;
        dfs(root);
        return ans-1;
        //在求深度基础之上进行求直径，最后l+r要减一
        //错误解答： 最大直径是左子树和右子树的最大深度之和，但是万一最大直径没有经过根节点呢？
        //所以说对于树中的每一个结点，都要把它视为根节点，然后比较所有结点的左子树和右子树的最大深度之和，取其中的最大值。
    }
    public int dfs(TreeNode node){
        if(node==null)
            return 0;
        int l=dfs(node.left);
        int r=dfs(node.right);
        ans=Math.max(ans,l+r+1);
        //对于树中的每一个结点，都要把它视为根节点，然后比较所有结点的左子树和右子树的最大深度之和，取其中的最大值。
        return Math.max(l,r)+1;//叶子结点l和r都为0，所以返回1，
    }
}

124. 二叉树中的最大路径和

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：
树专题 - 图9
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
树专题 - 图10
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

class Solution {
    int ans=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode root){
        if(root==null)
            return 0;
        int left=dfs(root.left);
        int right=dfs(root.right);
        ans=Math.max(ans,left+root.val+right);//比较当前结点和ans，更新ans
        return Math.max(0,root.val+Math.max(left,right));//返回大于0的结点值，否则就返回0
    }
}

173. 二叉搜索树迭代器

难度中等322
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示：

next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

利用中序遍历的非递归用栈的思想：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    Deque<TreeNode> stack =new LinkedList<TreeNode>();

    public BSTIterator(TreeNode root) {
        while(root!=null){
            stack.push(root);
            root=root.left;
        }
    }

    public int next() {
        TreeNode p=stack.pop();
        int res=p.val;
        p=p.right;
        while(p!=null){
            stack.push(p);
            p=p.left;
        }
        return res;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：
树专题 - 图12
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[1,2]

public class Codec {
    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode rdeserialize(List<String> l) {
        if (l.get(0).equals("None")) {
            l.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
        l.remove(0);
        root.left = rdeserialize(l);
        root.right = rdeserialize(l);

        return root;
    }

    public TreeNode deserialize(String data) {
        String[] data_array = data.split(",");
        List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
        return rdeserialize(data_list);
    }
}