6. 二叉树的下一个节点

题目描述

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

解题思路

二叉树中序遍历顺序为 左中右

把传入的当前结点看做中结点，则：下一个节点为有两种况

  1. 当前结点的右结点为空，则下一个结点是当前节的父结点/祖先结点；
    • 当父结点的左结点等于当前结点时，当前结点的一个结点为父结点；
    • 当父结点的左结点不等于当前结点时，继续找父点的父结点；
  2. 当前结点的右结点不为空，则当前节点有右子树则下一个结点为右子树的最左结点

代码实现

java 代码

    /**
     * 二叉树结点
     */
    public class TreeLinkNode {
        int val; //当前结点值
        TreeLinkNode left = null;//当前结点的左结点
        TreeLinkNode right = null;//当前结点的右结点
        TreeLinkNode next = null;//当前结点的父结点

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

    /**
     * 给定一个二叉树和其中的一个结点，找出中序遍历顺序的下一个结点并且返回
     * 二叉树中序遍历顺序为 左中右
     * 把传入的当前结点看做中，则：下一个节点为有两种情况
     * 1. 当前结点的右结点为空，则下一个结点是当前节点的父结点/祖先结点；
     *  - 当父结点的左结点等于当前结点时，当前结点的下一个结点为父结点；
     *  - 当父结点的左结点不等于当前结点时，继续找父结点的父结点；
     * 2. 当前结点的右结点不为空，则当前节点有右子树，则下一个结点为右子树的最左结点
     *
     * @param pNode
     * @return
     */
    public TreeLinkNode getNext(TreeLinkNode pNode) {
        if (pNode.right == null) {
            while (pNode.next != null) {
                if (pNode == pNode.next.left) {
                    return pNode.next;
                }
                pNode = pNode.next;
            }
            return null;
        } else {
            TreeLinkNode node = pNode.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
    }

    public static void main(String[] args){
        TreeLinkNode root = new TreeLinkNode(1);
        TreeLinkNode node2 = new TreeLinkNode(2);
        TreeLinkNode node3 = new TreeLinkNode(3);
        TreeLinkNode node4 = new TreeLinkNode(4);
        TreeLinkNode node5 = new TreeLinkNode(5);
        TreeLinkNode node6 = new TreeLinkNode(6);
        TreeLinkNode node7 = new TreeLinkNode(7);
        TreeLinkNode node8 = new TreeLinkNode(8);
        node4.right = node7;
        node2.left = node4;
        root.left = node2;
        node6.left = node8;
        node3.left = node5;
        node3.right = node6;
        root.right = node3;
        System.out.println(getNext(node4).val);
    }

Kotlin 代码

    /**
     * 二叉树结点
     */
    class TreeLinkNode(val value: Int) {
        var left: TreeLinkNode? = null //当前结点的左结点
        var right: TreeLinkNode? = null //当前结点的右结点
        var next: TreeLinkNode? = null //当前结点的父结点
    }

    /**
     * 给定一个二叉树和其中的一个结点，找出中序遍历顺序的下一个结点并且返回
     * 二叉树中序遍历顺序为 左中右
     * 把传入的当前结点看做中，则：下一个节点为有两种情况
     * 1. 当前结点的右结点为空，则下一个结点是当前节点的父结点/祖先结点；
     * - 当父结点的左结点等于当前结点时，当前结点的下一个结点为父结点；
     * - 当父结点的左结点不等于当前结点时，继续找父结点的父结点；
     * 2. 当前结点的右结点不为空，则当前节点有右子树，则下一个结点为右子树的最左结点
     *
     * @param pNode
     * @return
     */
    private fun getNext(pNode: TreeLinkNode?): TreeLinkNode? {
        var pNode = pNode
        return if (pNode!!.right == null) {
            while (pNode!!.next != null) {
                if (pNode === pNode.next!!.left) {
                    return pNode.next
                }
                pNode = pNode.next
            }
            null
        } else {
            var node = pNode.right
            while (node!!.left != null) {
                node = node.left
            }
            node
        }
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val root = TreeLinkNode(1)
        val node2 = TreeLinkNode(2)
        val node3 = TreeLinkNode(3)
        val node4 = TreeLinkNode(4)
        val node5 = TreeLinkNode(5)
        val node6 = TreeLinkNode(6)
        val node7 = TreeLinkNode(7)
        val node8 = TreeLinkNode(8)
        node4.right = node7
        node2.left = node4
        root.left = node2
        node6.left = node8
        node3.left = node5
        node3.right = node6
        root.right = node3
        println(getNext(node4)?.value)
    }

引用声明

该题目引用自
牛客网