leetcode - 04 树专题 114~106~96~863~剑指Offer 27~257~108~617~ 剑指 Offer 07 重建二叉树~99

114. 二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        while (root!=null){
            // 重复处理
            TreeNode pNode = root.left;
            if(pNode != null){
                // 找到root节点左子树的右子树的最右侧节点
                while (pNode.right!=null){
                    pNode = pNode.right;
                }
                // pNode的右子节点指向root的右子节点
                pNode.right = root.right;
                // root的右子节点执行root的左子节点
                root.right = root.left;
                // root的左子节点置为null
                root.left = null;
            }
            root = root.right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

class Solution {
    HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inleft = 0;
        int inrignt = inorder.length-1;
        int postleft = 0;
        int postright = postorder.length-1;

        for (int i=0;i<inorder.length;i++) {
            map.put(inorder[i],i);
        }
        return rebuild(inleft,inrignt,postleft,postright,postorder,inorder);
    }

    private TreeNode rebuild(int inleft, int inrignt,  int postleft, int postright, int[] postorder, int[] inorder) {
        if(inleft>inrignt || postleft>postright){
            return null;
        }
        int rootValue = postorder[postright];
        TreeNode root = new TreeNode(rootValue);
        int index = map.get(rootValue);
        root.left = rebuild(inleft,index-1,postleft,postleft+index-inleft-1,postorder,inorder);
        root.right = rebuild(index+1,inrignt,postleft+index-inleft,postright-1,postorder,inorder);
        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

96. 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        // G(n) = G(0)*G(n-1) + G(1)*G(n-2) + ... +G(n-1)*G(0)
        // 动态规划
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                // G(n) = G(0)*G(n-1) + G(1)*G(n-2) + ... + G(n-1)*G(0)
                //dp[2] = dp[0]*dp[1] +  dp[1]*dp[0]
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

863. 二叉树中所有距离为 K 的结点

class Solution {
    Map<Integer, TreeNode> map = new HashMap<>();
    List<Integer> res = new ArrayList<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        // 从root出发dfs记录每个节点的父节点
        findParant(root);
        // 从target出发dfs寻找所有深度为k的节点
        TreeNode from = null;
        int depth = 0;
        findRes(target,from,depth,k);
        return res;
    }

    private void findRes(TreeNode node, TreeNode from, int depth, int k) {
        if(node==null){
            return;
        }
        if(depth==k){
            res.add(node.val);
            return;
        }
        if(node.left!=from){
            findRes(node.left,node,depth+1,k);
        }
        if(node.right!=from){
            findRes(node.right,node,depth+1,k);
        }
        if(map.get(node.val) != from){
            findRes(map.get(node.val),node,depth+1,k);
        }
    }


    private void findParant(TreeNode node) {
        if(node.left!=null){
            map.put(node.left.val,node);
            findParant(node.left);
        }
        if(node.right!=null){
            map.put(node.right.val,node);
            findParant(node.right);
        }
    }
}
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

剑指 Offer 27. 二叉树的镜像

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

257. 二叉树的所有路径

方法1：

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root,"",res);
        return res;
    }

    private void dfs(TreeNode root, String path, List<String> res) {
        if(root==null){
            return;
        }
        // 到达根节点，将路径添加到res
        if(root.left==null && root.right==null){
            res.add(path+root.val);
            return;
        }
        // 不是叶子节点，分别遍历左右节点
        dfs(root.left,path+root.val+"->",res);
        dfs(root.right,path+root.val+"->",res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法2：

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        Stack<Object> stack = new Stack<>();
        // 将节点的入栈
        stack.push(root);
        // 将节点路径入栈
        stack.push(root.val+"");
        while (!stack.isEmpty()){
            String path = (String)stack.pop();
            TreeNode node = (TreeNode)stack.pop();
            if(node.left==null && node.right==null){
                // 说明是叶子节点
                res.add(path);
            }
            if(node.left!=null){
                stack.push(node.left);
                stack.push(path+"->"+node.left.val);
            }
            if(node.right!=null){
                stack.push(node.right);
                stack.push(path+"->"+node.right.val);
            }
        }
        return res;
    }
}
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

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0){
            return null;
        }
        int left  = 0;
        int right = nums.length-1;
       return dfs(nums,left,right);
    }

    private TreeNode dfs(int[] nums, int left, int right) {
        if(left>right){
            return null;
        }
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums,left,mid-1);
        root.right = dfs(nums,mid+1,right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

617. 合并二叉树

方法1：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null || root2==null){
            return root1==null ? root2 : root1;
        }
        return dfs(root1,root2);
    }

    private TreeNode dfs(TreeNode root1, TreeNode root2) {
        if(root1==null || root2==null){
            return root1==null ? root2 : root1;
        }
        root1.val = root1.val+root2.val;
        root1.left = dfs(root1.left,root2.left);
        root1.right = dfs(root1.right,root2.right);
        return root1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer 07. 重建二叉树

class Solution {
    HashMap<Integer,Integer> map = new HashMap<>()
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLeft = 0;
        int preRight = preorder.length-1;
        int inLeft= 0;
        int inRight = inorder.length-1;
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return dfs(preLeft,preRight,preorder,inLeft,inRight,inorder,map);
    }

    private TreeNode dfs(int preLeft, int preRight, int[] preorder, int inLeft, int inRight, int[] inorder, HashMap<Integer, Integer> map) {
        if(inLeft>inRight || preLeft>preRight){
            return null;
        }
        int rootValue = preorder[preLeft];
        TreeNode root = new TreeNode(rootValue);

        Integer index = map.get(rootValue);

        root.left = dfs(preLeft+1,preLeft+index-inLeft,preorder,inLeft,index-1,inorder,map);
        root.right = dfs(preLeft+index-inLeft+1,preRight,preorder,index+1,inRight,inorder,map);
        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

99. 恢复二叉搜索树

class Solution {

    public void recoverTree(TreeNode root) {
        // 获取中序遍历结果
        List<TreeNode> list = new ArrayList<>();
        dfs(root,list);
        // 找出中序遍历中错误顺序的两个数
        TreeNode x = null;
        TreeNode y = null;
        for(int i = 0;i<list.size()-1;i++){
            if(list.get(i).val>list.get(i+1).val){
                y = list.get(i+1);
                if(x==null){
                    x = list.get(i);
                }
            }
        }
        // 交换x和y
        if(x!=null && y!=null){
            int temp = x.val;
            x.val = y.val;
            y.val = temp;
        }
    }

    private void dfs(TreeNode root, List<TreeNode> list) {
        if(root==null){
            return;
        }
        dfs(root.left,list);
        list.add(root);
        dfs(root.right,list);
    }
}
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

429. N 叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){
            return new ArrayList<>();
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<size;i++){
                Node node = queue.poll();
                list.add(node.val);
                List<Node> children = node.children;
                for (Node child : children) {
                    queue.add(child);
                }
            }
            res.add(list);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums==null || nums.length==0){
            return null;
        }
        int left = 0;
        int right = nums.length-1;
        return buildTree(nums,left,right);
    }

    private TreeNode buildTree(int[] nums,int left, int right) {
        if(left>right){
            return null;
        }
        int mid = left+(right-left)/2;

        // 创建节点
        TreeNode root = new TreeNode(nums[mid]);
        // 递归处理左右子树
        root.left = buildTree(nums,left,mid-1);
        root.right = buildTree(nums,mid+1,right);
        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

109. 有序链表转换二叉搜索树

class Solution {
    public TreeNode sortedListToBST( ListNode head) {
       return buildTree(head,null);
    }

    private TreeNode buildTree(ListNode left, ListNode right) {
        if(left==right){
            return null;
        }

        // 获取链表的中间节点
        ListNode midNode = getMidNode(left,right);

        // 创建根节点
        TreeNode root = new TreeNode(midNode.val);

        // 递归处理子树
        root.left = buildTree(left,midNode);
        root.right = buildTree(midNode.next,right);
        return root;
    }

    private ListNode getMidNode(ListNode left,ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next!=right){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
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

701. 二叉搜索树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        if(val>root.val) {
            // 插入右子树
            root.right = insertIntoBST(root.right, val);
        }else {
            // 插入左子树
            root.left = insertIntoBST(root.left,val);
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

530. 二叉搜索树的最小绝对差

class Solution {
    int minValue = Integer.MAX_VALUE;
    int pre = -1;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return minValue;
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        // 中序遍历时递增序列
        dfs(root.left);
        if(pre == -1){
            pre = root.val;
        }else{
            minValue = Math.min(minValue,root.val-pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) {
            map.put(postorder[i],i);
        }
        int pre_start = 0;
        int pre_end = preorder.length-1;
        int post_start = 0;
        int post_end = postorder.length-1;
        return rebuilder(pre_start,pre_end,post_start,post_end,preorder,postorder,map);
    }

    private TreeNode rebuilder(int pre_start, int pre_end, int post_start, int post_end, int[] preorder, int[] postorder, Map<Integer, Integer> map) {
        if(pre_start>pre_end || post_start>post_end){
            return null;
        }
        int rootValue = preorder[pre_start];
        TreeNode root = new TreeNode(rootValue);

        if(pre_start==pre_end){
            return root;
        }

        int index = map.get(preorder[pre_start+1]);
        root.left = rebuilder(pre_start+1,pre_start+1+(index-post_start),post_start,index,preorder,postorder,map);
        root.right = rebuilder(pre_start+1+(index-post_start)+1,pre_end,index+1,post_end-1,preorder,postorder,map);
        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