二叉树

发表于 | 分类于 |

二叉树的前序遍历

递归实现

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
/**
 * 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 Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        preOrder(root, res);

        return res;
    }

    private void preOrder(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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 Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        //创建一个栈，用来存放结点
        Deque<TreeNode> stack = new ArrayDeque<>();
        //将根节点放入
        stack.push(root);
        while(!stack.isEmpty()){
            //弹出一个结点
            TreeNode node = stack.pop();
            //将弹出的结点保存在List中
            res.add(node.val);

            //压入该结点的右子结点、左子结点
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }

        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
28
29
30
31
32
33
34
35
36
/**
 * 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 Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        inOrder(root, res);

        return res;
    }

    private void inOrder(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }

        inOrder(root.left, res);
        res.add(root.val);
        inOrder(root.right, 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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 Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root != null || !stack.isEmpty()){
            //保存左子节点
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                //弹出一个结点
                TreeNode node = stack.pop();
                //将结点保存在list中
                res.add(node.val);
                //访问右子节点
                root = node.right;
            }
        }

        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
28
29
30
31
32
33
34
35
36
/**
 * 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 Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        postorder(root, res);

        return res;
    }

    private void postorder(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

二叉树的层序遍历

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
/**
 * 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 Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //创建一个list
            List<Integer> list = new ArrayList<>();
            //当前层的节点个数
            int size = queue.size();
            for(int i = 0; i < size; i++){
                //取出结点
                TreeNode node = queue.poll();
                //加入List
                list.add(node.val);
                //加入左子节点和右子节点
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            //将list加入res
            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
25
26
/**
 * 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 Solution {
    public int maxDepth(TreeNode root) {
        //边界条件，递归出口
        if(root == null){
            return 0;
        }
		
        //递归调用，返回左子树和右子树最深的+1
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

对称二叉树

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
/**
 * 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 Solution {
    public boolean isSymmetric(TreeNode root) {
        //根结点为null，也返回true
        if(root == null){
            return true;
        }

        return isTrue(root.left, root.right);
    }
    
    private boolean isTrue(TreeNode left, TreeNode right){
        //如果左子树和右子树都为null，则返回true
        if(left == null && right == null){
            return true;
            //其中一个为null，则返回false
        }else if(left == null || right == null){
            return false;
            //左子树的值和右子树的值不等则返回false
        }else if(left.val != right.val){
            return false;
        }

        //递归调用,左子树的左子节点和右子树的右子结点比较，左子树的右子节点和右子树的左子节点比较
        return isTrue(left.left, right.right) && isTrue(left.right, right.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
/**
 * 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 Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //若根结点为null，则返回false
        if(root == null){
            return false;
        }

        //若结点到了叶子结点即没有右结点和左结点时,targetSum = root.val则返回true
        if(root.left == null && root.right == null){
            return root.val == targetSum;
        }

        //递归调用，在左子树中搜索或在右子树中搜索
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

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

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
/**
 * 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 Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //边界条件，递归出口
        if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0){
            return null;
        }
        // 数组的长度
        int length = inorder.length;
        //后续遍历中最后一个元素为根节点
        TreeNode root = new TreeNode(postorder[length-1]);
        //遍历中序序列
        for(int i = 0; i < length; i++){
            //在中序序列中找到根结点
            if(inorder[i] == root.val){
                //递归调用，来构造左子树和右子树
                root.left = buildTree(Arrays.copyOfRange(inorder, 0, i), Arrays.copyOfRange(postorder, 0, i));
                root.right = buildTree(Arrays.copyOfRange(inorder, i+1, length), Arrays.copyOfRange(postorder, i, length - 1));
            }
        }

        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
/**
 * 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 Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //边界条件，递归出口
        if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0){
            return null;
        }

        //数组序列长度
        int length = preorder.length;
        //构建一个root结点，结点中的值为前序遍历中第一个元素
        TreeNode root = new TreeNode(preorder[0]);
        //遍历中序序列，找到根节点
        for(int i = 0; i < length; i++){
            if(inorder[i] == root.val){
                //递归调用
                root.left = buildTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i));
                root.right = buildTree(Arrays.copyOfRange(preorder, i+1, length), Arrays.copyOfRange(inorder, i+1, length));
            }
        }

        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
58
59
60
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        //边界条件
        if(root == null){
            return root;
        }

        //构建一个队列进行层序遍历
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            //查看该层的结点个数
            int size = queue.size();
            for(int i = 0; i < size; i++){
                //取队列中的一个元素
                Node node = queue.poll();

                //判断当前结点是否是最后一个
                if(i < size - 1){
                    //将当前结点的next指向同层另一个结点
                    node.next = queue.peek();
                }

                //将当前结点的左子树和右子树加入队列中
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.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
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
/**
 * 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) {
        //边界条件，p结点或q结点是否为根节点，若为根节点则直接返回root
        if(root == null || p == root || q == root){
            return root;
        }

        //判断p结点是在左子树还是右子树
        boolean pInLeft = findNode(root.left, p) != null;
        boolean pInRight = !pInLeft;
        //判断q结点是在左子树还是右子树
        boolean qInLeft = findNode(root.left, q) != null;
        boolean qInRight = !qInLeft;

        //q和p结点都在左子树，则递归调用
        if(pInLeft && qInLeft){
            return lowestCommonAncestor(root.left, p , q);
        }

        //q和p结点都在右子树
        if(pInRight && qInRight){
            return lowestCommonAncestor(root.right, p, q);
        }

        return root;

    }

    //在树中寻找指定结点
    private TreeNode findNode(TreeNode root, TreeNode node){
        //边界条件
        if(root == null || root == node){
            return root;
        }

        //递归调用，分别在左子树和右子树中查找
        TreeNode LNode = findNode(root.left, node);
        TreeNode RNode = findNode(root.right, node);

        return LNode == null ? RNode : LNode;
    }
}

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

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serialize(root, new StringBuilder()).toString();
        }

    private StringBuilder serialize(TreeNode root, StringBuilder sb){
        //边界条件，递归的出口
        if(root == null){
            return sb.append("None,");
        }

        //前序遍历，记录根节点
        sb.append(root.val).append(",");
        //递归记录左子树，右子树
        sb = serialize(root.left, sb);
        sb = serialize(root.right, sb);

        return sb;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //将String -> String[]
        String[] stringArray = data.split(",");
        //将String[] -> list
        List<String> list = new LinkedList<>(Arrays.asList(stringArray));
        return deserialize(list);
    }

    private TreeNode deserialize(List<String> list){
        //取出list中的首个元素，若为null，则直接返回
        if(list.get(0).equals("None")){
            list.remove(0);
            return null;
        }

        //构建一个root结点
        TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        //构建左子树
        root.left = deserialize(list);
        //构建右子树
        root.right = deserialize(list);

        return root;
    }
}
Donate comment here