[剑指OFFER]之树:JZ8 二叉树的下一个结点

[剑指OFFER]之树:JZ8 二叉树的下一个结点,第1张

文章目录
  • @[TOC]
  • 1.题目
  • 2.解法
    • 2.1 树的结构
    • 2.2 解法1
    • 2.3 解法2
  • 总结
1.题目

给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示,从子节点指向父节点的用虚线表示

2.解法 2.1 树的结构
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) {
        
    }
}
2.2 解法1

定义一个中序遍历的方法,在遍历时把顺序记录到List intravels中,在GetNext方法内,通过下标关系来获取下一个。

缺点,浪费空间O(n)。

 public void intravel(TreeLinkNode node, List<TreeLinkNode> intravels) {
        if(node==null) return;

        intravel(node.left,intravels);
        intravels.add(node);
        intravel(node.right,intravels);
    }

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        List<TreeLinkNode> intravels = new LinkedList<>();
        TreeLinkNode root = pNode;
        while (root.next!=null){
            root = root.next;
        }
        intravel(root,intravels);
        int pos = intravels.indexOf(pNode);
        if(pos==-1||pos==intravels.size()-1) return null;
        TreeLinkNode nextNode = intravels.get(pos+1);
        return nextNode;
    }
2.3 解法2

分情况讨论。

中序遍历的特点是,要先左子树,然后是根,然后右子树。

一、如果该节点有右子树,那么接下来,就是访问右子树咯。对于右子树而言,会持续递归找到其最左叶子,这个节点就是next元素了。

二、如果该节点没有右子树,这时,就又分两种情况

A、pNode对于父节点而言,是父节点的左子树,此时返回父节点。

B、pNode对于父节点而言,是父节点的右子树。这就比较麻烦。要持续找到祖先,且祖先是一个左孩子,返回祖先的父节点。

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //如果该节点有右子树,最左子树的叶子
        if (pNode.right != null) {
            TreeLinkNode target = pNode.right;
            while (target.left != null) {
                target = target.left;
            }
            return target;
        }

        //如果该节点没有右子树
        //那么分为两种情况,
        if (pNode.next != null) {
            //1,自己是父节点的左子树,返回父节点
            if (pNode.next.left == pNode) return pNode.next;
            //2.自己是父节点的右子树,则先找父节点,然后看父节点是左派还是右派。
            TreeLinkNode parent = pNode.next;
            //找到不是右子树的祖先
            while (parent.next != null) {
                if (parent == parent.next.right)
                    parent = parent.next;
                else
                    break;
            }
            //终于找到祖先不是右子树了。
            //返回祖先的父亲
            return parent.next;
        }
        return null;
    }
总结

如果要节约空间,就要对pNode的位置进行讨论分类。三类情况,最后一种最复杂。

算法系列在github上有一个开源项目,主要是本系列博客的demo代码。https://github.com/forestnlp/alg
如果您对软件开发、机器学习、深度学习有兴趣请关注本博客,将持续推出Java、软件架构、深度学习相关专栏。
您的支持是对我最大的鼓励。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/792776.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存