牛客网——剑指offer之二叉树的下一个结点

LeetCode

题目

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

题解

这道题其实理解中序遍历的话就很简单，针对各种情况做不同的选择

  • 如果给定的点是根节点的话
    • 判断根节点的右孩子是否存在，若存在则已有孩子为起点，查找最左节点
    • 如果右孩子不存在，则直接返回null
  • 如果给定的节点是父节点的左孩子
    • 判断节点是否存在右孩子节点，如果存在，则返回右孩子
    • 如果不存在，则返回父节点
  • 如果给定的节点是父节点的右孩子
    • 节点的右孩子是否存在，如果存在直接返回右孩子
    • 如果右孩子不存在，判断是否是最右节点，是的话直接返回null
    • 否则，返回父节点的父节点

AC代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.LinkedList;
import java.util.Objects;

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "TreeLinkNode{" +
                "val=" + val +
                '}';
    }
}

public class Solution {

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 如果是根节点
        if (pNode.next == null) {
            return left(pNode.right);
        }
        // 如果是父节点的左孩子
        if (Objects.equals(pNode.next.left, pNode)) {
            if (pNode.right == null) {
                return pNode.next;
            }
            return pNode.right;
        }
        // 如果是父节点的右孩子
        else {
            if (pNode.right != null) {
                return pNode.right;
            }
            if (isRightBranch(pNode)) {
                return null;
            }
            return pNode.next.next;
        }
    }

    private TreeLinkNode left(TreeLinkNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node;
        }
        return left(node.left);
    }

    private boolean isRightBranch(TreeLinkNode node) {
        TreeLinkNode parent = node.next;
        if (parent == null) {
            return true;
        }
        if (Objects.equals(parent.right, node)) {
            return isRightBranch(parent);
        }
        return false;
    }

    public static void main(String[] args) {
        String[] val = new String[]{"8","6", "10","5","7","9", "11"};
        String[] val2 = new String[]{"5","4","#","3","#","2"};
        val = val2;
        TreeLinkNode root = new TreeLinkNode(Integer.valueOf(val[0]));
        LinkedList<TreeLinkNode> queue = new LinkedList<>();
        LinkedList<TreeLinkNode> elements = new LinkedList<>();
        elements.add(root);
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < val.length) {
            String v1 = val[i ++];
            TreeLinkNode left = null;
            TreeLinkNode right = null;
            TreeLinkNode node = queue.removeFirst();
            if (!"#".equals(v1)) {
                left = new TreeLinkNode(Integer.valueOf(v1));
                left.next = node;
                queue.add(left);
                elements.add(left);
            }
            if (i < val.length) {
                String v2 = val[i ++];
                if (!"#".equals(v2)) {
                    right = new TreeLinkNode(Integer.valueOf(v2));
                    right.next = node;
                    queue.add(right);
                    elements.add(right);
                }
            }
            node.left = left;
            node.right = right;
        }
        print(root);

        Solution s = new Solution();
        TreeLinkNode target = elements.get(1);
        System.out.println(target);
        System.out.println(s.GetNext(target));
    }

    private static void print(TreeLinkNode node) {
        if (node != null) {
            print(node.left);
            System.out.println(node.val + ", " + node.next);
            print(node.right);
        }
    }

}