算法-二叉树

发表于 | 分类于 ，

算法中关于二叉树的有很多，将最近做的关于二叉树相关的算法整理下，以备查看。

Path Sum问题

Path Sum 112

给定一个二叉树和一个sum值，返回true如果存在一个从根节点到叶子节点的路径，否则返回false。

1
2
3
4
5
6
7
8
9
public class PathSum_112 {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
            return sum == root.val;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Path SumII 113

给定一个二叉树和一个sum值，找到所有的从根节点到叶子节点的路径和为sum的路径并返回。

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
package leetcode.binaryTree;
import leetcode.linkedList.ListNode;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class PathSumII_113 {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        getPathSum(root, sum, res,list);
        return res;
    }
    /**
     *
     * @param root 跟节点
     * @param sum 和
     * @param res 返回的二维数组
     * @param list 单个路径
     */
    private void getPathSum(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {
        if (root == null)
            return;
        list.add(root.val);
        //递归到叶子节点进行判断，决定是否将当前list添加到列表中，不是叶子节点则继续递归左子树和右子树。
        if (root.left == null && root.right == null && sum == root.val) {
            res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        } else {
            getPathSum(root.left, sum - root.val, res, list);
            getPathSum(root.right, sum - root.val, res, list);
        }
        //添加完记得删除，回溯上一个状态。
        list.remove(list.size() - 1);
    }
}

Path SumIII 437

给定一个二叉树，节点值可以为负数，找到路径和等于sum的路径的个数，其中路径不需要从根节点开始，也不需要从叶子节点终止。

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
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class PathSumIII_437 {
    public int pathSum(TreeNode root, int sum) {
        int res = 0;
        if (root == null)
            return res;
        res = findPath(root, sum);
        res += pathSum(root.left, sum);
        res += pathSum(root.right ,sum);
        return res;
    }
    private int findPath(TreeNode root, int sum) {
        if (root == null)
            return 0;
        int res = 0;
        if (root.val == sum)
            res++;
        return res + findPath(root.left, sum - root.val) + findPath(root.right, sum - root.val);
    }
}

树的深度问题

树的最大深度问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class MaximunDepthOfBinaryTree_104 {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int leftMaxDepth = maxDepth(root.left);
        int rightMaxDepth = maxDepth(root.right);
        return Math.max(leftMaxDepth, rightMaxDepth) + 1;
    }
}

树的最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class MinimumDepthOfBinaryTree_111 {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left == null)
            return 1 + minDepth(root.right);
        if (root.right == null)
            return 1 + minDepth(root.left);
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

二叉树的最早祖先节点

1
2
3
4
5
6
7
8
9
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 root;
    return left != null ? left : right;
}

二叉搜索树的最早祖先节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class LowestCommonAncestorOfABinarySearchTree_235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        else if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

二叉搜索树

二叉搜索树第k小的节点

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
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
import java.util.Stack;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class KthSmallestElementInaBST_230 {
    //堆栈方法
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (root != null) {
            stack .push(root);
            root = root.left;
        }
        while (k != 0) {
            TreeNode node = stack.pop();
            k--;
            if (k == 0)
                return node.val;
            TreeNode right = node.right;
            while (right != null) {
                stack.push(right);
                right = right.left;
            }
        }
        return -1;
    }
    //递归方法
    public int kthSmallest1(TreeNode root, int k) {
        int count = countNodes(root.left);
        if (k <= count)
            return kthSmallest(root.left, k);
        else if (k > count + 1)
            return kthSmallest(root.right, k - 1 -count);
        return root.val;
    }
    private int countNodes(TreeNode left) {
        if (left == null)
            return 0;
        return 1 + countNodes(left.left) + countNodes(left.right);
    }
}

检验一棵树是否为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class ValidateBST_98 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode root, long minValue, long maxValue) {
        if (root == null)
            return true;
        if (root.val >= maxValue || root.val <= minValue)
            return false;
        return isValidBST(root.left,minValue, root.val) && isValidBST(root.right, root.val, maxValue);
    }
}

从二叉搜索树里面删除一个节点

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
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class DeleteNodeInABST_450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (key < root.val)
            root.left = deleteNode(root.left, key);
        else if (key > root.val)
            root.right = deleteNode(root.right, key);
        else {
            if (root.left == null) {
                return root.right;
            }else if (root.right == null) {
                return root.left;
            }
            TreeNode min = find(root.right);
            root.val = min.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    private TreeNode find(TreeNode root) {
        while (root.left != null)
            root = root.left;
        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
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class BalancedBinaryTree_110 {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.abs(right - left) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(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
24
25
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class ConvertSortedArrayToBST_108 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0)
            return null;
        return help(nums, 0, nums.length-1);
    }
    private TreeNode help(int[] nums, int low, int high) {
        if (low > high)
            return null;
        int mid = (low + high) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = help(nums, low, mid - 1);
        root.right = help(nums, mid + 1, high);
        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
55
56
57
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class CountCompleteTreeNode_222 {
    public int countNodes(TreeNode root) {
        int h = getHeight(root);
        int nodes = 0;
        while (root != null) {
            if (getHeight(root.right) == h - 1){
                nodes += 1 << h;
                root = root.right;
            } else {
                nodes += 1 << h - 1;
                root = root.left;
            }
            h--;
        }
        return nodes;
    }
    private int getHeight(TreeNode root) {
        if (root == null)
            return -1;
        return 1 + getHeight(root.left);
    }
    //队列
    public int countNodes1(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 1;
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp.val != -1) {
                tmp.val = -1;
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                    count++;
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                    count++;
                }
            }
        }
        return count;
    }
}

反转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class InverseBinaryTree_226 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return null;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

相等的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class SameTree_100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null)
            return false;
        if (p.val == q.val)
            return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
        else
            return false;
    }
}

左叶子节点的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class SumOfLeftLeaves_404 {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null)
            return 0;
        if (root.left != null && root.left.left == null && root.left.right == null)
            return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(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
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
55
56
57
58
59
60
package leetcode.binaryTree;
import leetcode.linkedList.ListNode;
import leetcode.stack.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class SumRootToLeafNumbers_129 {
    public int sumNumbers(TreeNode root) {
        if (root == null)
            return 0;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        getPathSum(root, res, list);
        int result = 0;
        for (List<Integer> list1 : res) {
            int tmp = 0;
            for (Integer i : list1) {
                tmp = tmp * 10 + i;
            }
            result += tmp;
        }
        return result;
    }
    private void getPathSum(TreeNode root,List<List<Integer>> res, List<Integer> list) {
        if (root == null)
            return;
        list.add(root.val);
        if (root.left == null && root.right == null) {
            res.add(new ArrayList<>(list));
            list.remove(list.size() - 1);
            return;
        } else {
            getPathSum(root.left, res, list);
            getPathSum(root.right, res, list);
        }
        list.remove(list.size() - 1);
    }
    public int sumNumbers1(TreeNode root) {
        return sumNumbers(root, 0);
    }
    public int sumNumbers(TreeNode root, int sum) {
        if (root == null)
            return 0;
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
    }
}

镜像树问题

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
package leetcode.binaryTree;
import leetcode.stack.TreeNode;
/**
 * Created by cdx0312
 * 2018/4/9
 */
public class SymmetricTree_101 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isSymmetricHelp(root.left, root.right);
    }
    private boolean isSymmetricHelp(TreeNode left, TreeNode right) {
        if (left == null && right == null)
            return true;
        if (left == null || right == null)
            return false;
        if (left.val == right.val)
            return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right,right.left);
        return false;
    }
}
Donate comment here