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

剑指offer60天计划

Posted by liuwenzi on July 24, 2020
阅读数:

二叉树的下一个节点

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

题解

  • 分为三种情况

    • 当前节点有右子树
      • 找到当前节点的右子树中的最左节点
    • 当前节点没有右子树并且是其父节点的右子节点
      • 找到一个节点(A),当A为其父节点的左子节点时,A的父节点即为下一个节点
      • 否则,返回null
    • 否则,找到当前节点的父节点。
      • 其父节点即为下一个节点
      • 否则,返回null
    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
    
    /*
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
      
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if( pNode.right != null){
                pNode = pNode.right;
                while(pNode.left != null){
                     pNode = pNode.left;
                }
                return pNode;
            }else if(pNode.next != null && pNode.next.right == pNode){
                while(pNode.next != null && pNode != pNode.next.left){
                    pNode = pNode.next;
                }
                return pNode.next == null ? null:pNode.next;
            }else{
                return pNode.next == null ? null : pNode.next ;
            }
        }
    }
    

总结

需要熟悉二叉树的中序遍历,将对应的集中情况都考虑到。最好画出树,然后比划一下