剑指Offer-二叉树的下一个结点

朴灿烈づ我的快乐病毒、 2022-04-24 13:18 208阅读 0赞

## 题目描述 ##

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

解题思路—**回退遍历**：要求二叉树的中序遍历顺序的下一个结点，有以下3种情况：

> **1. 二叉树结点为空，返回null。  
> 2. 二叉树结点有右子树，则从右子树开始一直沿着指向左指针遍历，即右子树最左边的点就是下一个结点。  
> 3. 二叉树结点没有右子树，则要回退遍历。如果该结点是其父结点的左结点，则返回父结点；否则继续遍历父结点的父结点，直至遍历的节点是父结点的左结点，若没有，则表明该节点是中序遍历最后一个结点，返回null。**

解题思路—**中序遍历**：这是一个比较**简单暴力**的方法，从当前结点一直**回退遍历到树的根结点**，**从根结点开始中序遍历**，使用ArrayList**顺序保存每一个结点**，最后与pNode匹配，结果输出ArrayList中**pNode的下一个结点**即可。

## Java解题—回退遍历 ##

/*
    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==null)
                return null;
            if(pNode.right!=null){ // 结点有右子树
                pNode = pNode.right;
                while(pNode.left!=null)
                    pNode = pNode.left;
                return pNode;
            }
            while(pNode.next!=null){ // 结点没有右子树
                if(pNode.next.left==pNode)
                    return pNode.next;
                pNode = pNode.next;
            }
            return null; // 退回到根节点，仍然没有找到
        }
    }

## Java解题—中序遍历 ##

import java.util.ArrayList;
    public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode==null)
                return null;
            ArrayList<TreeLinkNode> list = new ArrayList<>();
            TreeLinkNode root = pNode;
            while(root.next!=null)   // 找树根
                root = root.next;
            mid(root, list);  // 中序遍历
            for(int i=0;i<list.size()-1;i++){
                if(list.get(i)==pNode)
                    return list.get(i+1);
            }
            return null;
        }
        
        public void mid(TreeLinkNode node, ArrayList<TreeLinkNode> list){
            if(node!=null){
                mid(node.left, list);
                list.add(node);
                mid(node.right, list);
            }
        }
    }