leetcode树

发表于 | 分类于

a搜索二叉树：左子树小于根节点，右子树大于根节点。

平衡树：左右子树高度差不大于1

一般解决二叉树的问题采用递归以及递归转非递归的方法。

98.验证二叉搜索树?

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
左子树的所有点应该在(minVal,root),右子树在(root,maxVal)
*/
public boolean isValidBST(TreeNode root) {
    return helper(root,Long.MIN_VALUE,Long.MAX_VALUE);
}

public boolean helper(TreeNode root,long minVal,long maxVal){
    if(root==null){
        return true;
    }
    if(root.val<=minVal||root.val>=maxVal){
        return false;
    }
    return helper(root.left,minVal,root.val)&&helper(root.right,root.val,maxVal);
}

还有一种做法：中序遍历结果是递增的，即为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public boolean isValidBST(TreeNode root) {
    boolean isRoot = true;
    if(root==null){
        return true;
    }
    Stack<TreeNode> stack = new Stack<>();
    int last = Integer.MIN_VALUE;
    while(!stack.isEmpty()||root!=null){
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        if(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(isRoot){
                last = node.val;
                isRoot = false;
            }else if(node.val>last){
                last = node.val;
            }else{
                return false;
            }
            //dayin
            root = node.right;
        }
    }
    return true;
}

144.前序非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while(!stack.isEmpty()||root!=null){
        while(root!=null){
            stack.push(root);
            result.add(root.val);
            root = root.left;
        }
        if(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            root = node.right;
        }
    }
    return result;
}

94.中序非递归遍历

1.将整棵树的左子树压入栈中

2.每次取出栈顶元素，如果他有右子树，则将右子树压入栈中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
     * 将root的最左的元素全部压入栈，当root==null，表示压到底了，最左侧已经没有元素了，此时，可以将栈顶元素取出
     * 并开始对右子树做同样操作
     * */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while(!stack.isEmpty()||root!=null){
        while (root!=null){
            stack.push(root);
            root = root.left;
        }
        if(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            root = node.right;
        }
    }
    return result;
}

144.后序非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * 前序根右左，反转为左右根即可
     * */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while(!stack.isEmpty()||root!=null){
        while(root!=null){
            result.add(0,root.val);
            stack.push(root);
            root = root.right;
        }
        if(!stack.isEmpty()){
            TreeNode node = stack.pop();
            root = node.left;
        }
    }
    return result;
}

101.对称二叉树?

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

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

递归做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
     * 两个根节点值相等
     * 左边的左子树和右边的右子树相等
     * 左边的右子树和右边的左子树相等
     * */
public boolean isSymmetric(TreeNode root) {
    //一般二叉树的题目首先判断是否null
    if(root==null){
        return true;
    }
    return helper(root,root);
}

public boolean helper(TreeNode p,TreeNode q){
    // 两个节点同时为空，返回true 只有一个节点为空，返回false
    if(p==null||q==null){
        return p==null&&q==null;
    }
    return p.val==q.val&&helper(p.left,q.right)&&helper(p.right,q.left);
}

非递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
     *对称树的话，对于根节点的左右子树分别进行左根右以及右左根应该是相同的
     * */
public boolean isSymmetric(TreeNode root) {
    if(root==null){
        return true;
    }
    return inOrder(root.left,root.right);
}

public boolean inOrder(TreeNode left ,TreeNode right){
    Stack<TreeNode> s_left = new Stack<>();
    Stack<TreeNode> s_right = new Stack<>();
    while (left!=null||right!=null||!s_left.isEmpty()||!s_right.isEmpty()){
        while(left!=null&&right!=null){
            s_left.push(left);
            s_right.push(right);
            left = left.left;
            right = right.right;
        }
        //假如left与right不等，表明左子树个数不一样，必定不同
        if(left!=right){
            return false;
        }

        if(s_left!=null&&s_right!=null){
            TreeNode leftnode = s_left.pop();
            TreeNode rightnode = s_right.pop();
            if(leftnode.val!=rightnode.val){
                return false;
            }
            left = leftnode.right;
            right = rightnode.left;
        }
    }
    return true;
}

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

递归的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public TreeNode buildTree(int[] preorder, int[] midorder) {
    //设置一个map存储索引位置，查询方便
    HashMap<Integer,Integer> midorder_index = new HashMap<>();
    for(int i=0;i<midorder.length;i++){
        midorder_index.put(midorder[i],i);
    }
    return helper(preorder,midorder,0,preorder.length-1,0,preorder.length-1,midorder_index);
}
/**
     * preorder[p_start]是根节点，这样就可以找到preorder[p_start]在中序遍历中的位置，这样，就可以获得左子树以及右子树的范围，接着递归来做
     * */
public TreeNode helper(int[] preorder , int[] midorder, int p_start, int p_end, int m_start, int m_end, Map<Integer,Integer> midorder_index){
    //此时没有元素了，直接返回null
    if(p_start>p_end){
        return null;
    }
    //获取根节点
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    int index = midorder_index.get(root_val);
    //左子树的长度
    int length = index - m_start;
    root.left = helper(preorder,midorder,p_start+1,p_start+length,m_start,index-1,midorder_index);
    root.right = helper(preorder,midorder,p_start+length+1,p_end,index+1,m_end,midorder_index);
    return root;

}

106. 从中序与后序遍历序列构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode buildTree(int[] inorder, int[] postorder) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<inorder.length;i++){
        map.put(inorder[i],i);
    }
    return helper3(inorder,postorder,0,inorder.length-1,0,inorder.length-1,map);
}
public TreeNode helper3(int[] inorder, int[] postorder,int i_start,int i_end,int p_start,int p_end,Map<Integer,Integer> map){
    if(i_start>i_end){
        return null;
    }
    if(i_start==i_end){
        return new TreeNode(postorder[p_start]);
    }
    int root_val = postorder[p_end];
    int index = map.get(root_val);
    int length = index - i_start;
    TreeNode root = new TreeNode(root_val);
    root.left = helper3(inorder,postorder,i_start,index-1,p_start,p_start+length-1,map);
    root.right = helper3(inorder,postorder,index+1,i_end,p_start+length,p_end-1,map);
    return root;
}

889. 根据前序和后序遍历构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public TreeNode constructFromPrePost(int[] pre, int[] post) {
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<pre.length;i++){
        map.put(post[i],i);
    }
    return helper2(pre,post,0,pre.length-1,0,pre.length-1,map);
}

public TreeNode helper2(int[] pre, int[] post, int pre_start, int pre_end, int post_start, int post_end, Map<Integer,Integer> map){
    if(pre_start>pre_end){
        return null;
    }
    if(pre_start==pre_end){
        return new TreeNode(pre[pre_start]);
    }

    int root_val = pre[pre_start];
    int left_val = pre[pre_start+1];
    int index = map.get(left_val);
    TreeNode root = new TreeNode(root_val);
    int length = index-post_start;
    root.left = helper2(pre,post,pre_start+1,pre_start+1+length,post_start,index,map);
    root.right  = helper2(pre,post,pre_start+1+length+1,pre_end,index+1,post_end-1,map);
    return root;
}

102.二叉树层次遍历?

通过队列来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if(root==null){
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while(queue.size()>0){
        List<Integer> vals = new ArrayList<>();
        int size = queue.size();
        for(int i=0;i<size;i++){
            TreeNode node = queue.remove();
            vals.add(node.val);
            if(node.left!=null) {
                queue.add(node.left);
            }
            if(node.right!=null) {
                queue.add(node.right);
            }
        }
        result.add(vals);
    }
    return result;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
     * 后序遍历二叉树。
     * 左子树返回不为空，右子树返回不为空，则该node必定是公共祖先
     * */
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //当前节点==p或者==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 root;
    }
    //只有一个子树返回的不是空
    return left!=null?left:right;
}

543.二叉树的直径

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

示例 :
给定二叉树

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
     * 某一个节点的直径=左子树深度+右子树深度
     * 树的深度 = max(左子树深度,右子树深度)+1
     * 因为要求任意两个节点的直径，所以还需要一个ans记录当前直径的最大值
     * */
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
    helper(root);
    return ans;
}
//helper返回的是树的深度，而直径最大值采用ans来记录
public int helper(TreeNode root){
    if(root==null){
        return 0;
    }
    //左右子树的深度
    int left = helper(root.left);
    int right = helper(root.right);
    //计算该点的直径，并与最大直径比较
    int zhijing = left+right;
    ans = zhijing>ans?zhijing:ans;
    //返回树的深度
    return (left>right?left:right)+1;
}

124.二叉树中最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 2:

输入: [-10,9,20,null,null,15,7]

-10
/
9 20
/
15 7

输出: 42

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int res=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    return helper(root);
}
public int helper(TreeNode root){
    if(root==null){
        return 0;
    }
    int left = helper(root.left);
    int right = helper(root.right);
    int root_res = left+right+root.val;
    res = Math.max(root_res,res);
    return Math.max(0,Math.max(left,right)+root.val);
}

173.二叉搜索树迭代器

可以用中序遍历来解决，但是要求空间复杂度为O(h)，h为树的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        int res = node.val;
        node = node.right;
        while(node!=null){
            stack.push(node);
            node = node.left;
        }
        return res;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

285.后继节点问题

1576680169342

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
     * 中序遍历：左根右
     * 所以，假如该节点有右子树，那么后继节点是右子树的最左一个节点
     * 假如该节点没有右子树，那么他一定是某一个节点p的左子树的最右节点，因此该节点后继节点就是p
     * */
public TreeNode getSuccessorNode(TreeNode node){
    if(node==null){
        return null;
    }
    if(node.right!=null){
        return getRightMostLeft(node.right);
    }else{
        TreeNode parent = node.parent;
        while(parent!=null&&parent.left!=node){
            node = node.parent;
            parent = node.parent;
        }
        return parent;
    }
}

public TreeNode getRightMostLeft(TreeNode node){
    while(node.left!=null){
        node = node.left;
    }
    return node;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public String serialize(TreeNode root) {
    if(root==null){
        return "#!";
    }
    String res = root.val+"!";
    res += serialize(root.left);
    res+= serialize(root.right);
    return res;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] values = data.split("!");
    Queue<String> queue = new LinkedList<>();
    for(String s:values){
        queue.add(s);
    }
    return recoverFromPre(queue);
}

public TreeNode recoverFromPre(Queue<String> queue){
    String value = queue.poll();
    if(value.equals("#")){
        return null;
    }else{
        TreeNode root = new TreeNode(Integer.parseInt(value));
        root.left = recoverFromPre(queue);
        root.right = recoverFromPre(queue);
        return root;
    }
}

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public String serialize(TreeNode root) {
    if(root==null){
        return "#!";
    }
    StringBuilder res=  new StringBuilder(root.val+"!");
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(queue.size()>0){
        TreeNode node = queue.poll();
        if(node.left!=null){
            queue.add(node.left);
            res.append(node.left.val+"!");
        }else{
            res.append("#!");
        }
        if(node.right!=null){
            queue.add(node.right);
            res.append(node.right.val+"!");
        }else{
            res.append("#!");
        }
    }
    return res.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] values = data.split("!");
    int index = 0;
    if(values[0].equals("#")){
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.parseInt(values[index++]));
    queue.add(root);
    while(queue.size()>0){
        TreeNode node =  queue.poll();
        String s_left = values[index++];
        String s_right = values[index++];
        if(s_left.equals("#")){
            node.left = null;
        }else{
            node.left = new TreeNode(Integer.parseInt(s_left));
            queue.add(node.left);
        }
        if(s_right.equals("#")){
            node.right = null;
        }else{
            node.right = new TreeNode(Integer.parseInt(s_right));
            queue.add(node.right);
        }
    }
    return root;
}

110. 平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isBalanced(TreeNode root) {
    isBalance = true;
    healperBalance(root);
    return isBalance;
}

private boolean isBalance = true;
//返回树的高度
public int  healperBalance(TreeNode root){
    if(root==null){
        return 0;
    }
    int left = healperBalance(root.left);
    int right = healperBalance(root.right);
    if(Math.abs(left-right)>1){
        isBalance = false;
    }
    return Math.max(left,right)+1;
}

958. 完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
     * 层序遍历，设置一个停止标志，遇到空节点，停止标志为真，如果停止标志为真，再遍历遇到非空节点，则非完全二叉树。
     * */
public boolean isCompleteTree(TreeNode root) {
    if(root==null){
        return true;
    }
    //当遇到第一个空节点时，将firstFull设置为true，假如是完全二叉树，后面所有节点都应该是空节点，不会再遇到非空节点
    boolean firstNull = false;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(queue.size()>0) {
        TreeNode node = queue.poll();
        if (node.left != null) {
            queue.add(node.left);
            //假如firstNull==true，该非空节点前面有一个空节点，必定不是完全二叉树
            if (firstNull) {
                return false;
            }
        } else {
            //第一个非空节点，记录标志
            if (!firstNull) {
                firstNull = true;
            }
        }
        if (node.right != null) {
            queue.add(node.right);
            if (firstNull) {
                return false;
            }
        } else {
            if (!firstNull) {
                firstNull = true;
            }
        }

    }
    return true;
}

222. 完全二叉树的节点个数?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
     * 寻找root右子树的最左节点，假如该节点位于最后一层，那么root的左子树必定是满二叉树，可以计算出节点个数，对于右子树，继续递归
     * 假如该节点位于倒数第二层，那么右子树是满二叉树，同理可计算
     * */
private int height = 0;
public int countNodes(TreeNode root) {
    if(root==null){
        return 0;
    }
    height = getHeight(root,1);
    return helpCount(root,1);
}
public int getHeight(TreeNode root,int level){
    while(root!=null){
        level++;
        root = root.left;
    }
    return level-1;
}
public int helpCount(TreeNode root,int level){
    if(level==height){
        return 1;
    }
    //获取右子树最左节点的层数
    int leftMostheight = getHeight(root.right,level+1);
    //最左节点位于最后一层，左子树是满二叉树
    if(leftMostheight==height){
        return (1<<(height-level))+helpCount(root.right,level+1);
    }else{
        return (1<<(height-level-1))+helpCount(root.left,level+1);
    }
}
  • 不判断root==null
  • ||以及&&的问题