0%

剑指offer008 二叉树的下一个节点

Posted on In Valine:

Problem:

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

1
2
3
4
5
6
7
8
9
10
11
public class TreeLinkNode {

    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null; // 指向父结点的指针

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

Intuition:

Solution:

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
public class CodingInterview_008 {
    class TreeLinkNode {

        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null; // 指向父结点的指针

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
     public TreeLinkNode GetNext(TreeLinkNode pNode){
         if(pNode.right!=null){
             TreeLinkNode node=pNode.right;
             while(node.left!=null){
                 node=node.left;
             }
             return node;
         }else{

             while(pNode.next!=null){
                 //注意下面的next是指向父节点
                 TreeLinkNode parent=pNode.next;
                 if(parent.left==pNode){
                     return parent;
                 }else{
                     pNode=parent;
                 }
             }
             return null;
         }
     }
}