牛客NC279 二叉树的下一个结点【中等 二叉树中序遍历 C++/Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e

思路

思路：

我们首先要根据给定输入中的结点指针向父级进行迭代，
直到找到该树的根节点；然后根据根节点进行中序遍历，当遍历到和给定树节点相同的节点时，
下一个节点就是我们的目标返回节点
具体做法：

step 1：首先先根据当前给出的结点找到根节点
step 2：然后根节点调用中序遍历
step 3：将中序遍历结果存储下来
step 4：最终拿当前结点匹配是否有符合要求的下一个结点

参考答案C++

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }
};
*/
class Solution {
  public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        //第一步：找到根节点
        TreeLinkNode* root = pNode;
        while (root->next != nullptr) {
            root = root->next;
        }

        //中序遍历找到pNode的下一个节点
        vector<TreeLinkNode*> stk;
        TreeLinkNode* prev = nullptr;
        while (stk.size() > 0 || root != nullptr) {
            while (root != nullptr) {
                stk.push_back(root);
                root = root->left;
            }

            int size = stk.size();
            root = stk[size - 1];
            if (prev != nullptr && prev == pNode) {
                return root;
            }
            vector<TreeLinkNode*> stkbak;
            for (int i = 0; i < size - 1; i++) {
                stkbak.push_back(stk[i]);
            }

            prev = root;
            root = root->right;
            stk = stkbak;
        }
        return nullptr;
    }
};

参考答案Java

import java.util.*;
/*
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) {
        /*
           思路：

           我们首先要根据给定输入中的结点指针向父级进行迭代，
           直到找到该树的根节点；然后根据根节点进行中序遍历，当遍历到和给定树节点相同的节点时，
           下一个节点就是我们的目标返回节点

           具体做法：

           step 1：首先先根据当前给出的结点找到根节点
           step 2：然后根节点调用中序遍历
           step 3：将中序遍历结果存储下来
           step 4：最终拿当前结点匹配是否有符合要求的下一个结点
            */

        //先找到根节点
        TreeLinkNode root = pNode;
        while (root.next != null) root = root.next;

        //中序遍历
        Stack<TreeLinkNode> stk = new Stack<>();
        TreeLinkNode pre = null;

        while (!stk.isEmpty() || root != null) {
            while (root != null) {
                stk.add(root);
                root = root.left;
            }

            root = stk.pop();

            if (pre != null && pre == pNode) {
                return root;
            }

            pre = root;

            root = root.right;
        }

        return null;
    }
}

参考答案Go

package main

/*
type TreeLinkNode struct {
    Val int
    Left *TreeLinkNode
    Right *TreeLinkNode
    Next *TreeLinkNode
}
*/

func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	//第一步：先找到根节点
	root := pNode
	for root.Next != nil {
		root = root.Next
	}

	//中序遍历找到pNode的下一个节点
	stk := []*TreeLinkNode{}
	var prev *TreeLinkNode = nil

	for len(stk) > 0 || root != nil {
		for root != nil {
			stk = append(stk, root)
			root = root.Left
		}

		size := len(stk)
		root = stk[size-1]
		stkbak := []*TreeLinkNode{}
		for i := 0; i < size-1; i++ {
			stkbak = append(stkbak, stk[i])
		}

		if prev != nil && prev == pNode {
			return root
		}

		prev = root
		stk = stkbak
        root=root.Right
	}
	return nil
}

参考答案PHP

<?php
/*class TreeLinkNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function GetNext($pNode)
{
   //第一步：找到根节点
    $root = $pNode;
    while ($root->next!=null) {
        $root = $root->next;
    }
    //中序遍历找到pNode的下一个节点
    $stk = [];
    $prev = null;
    while (count($stk) >0 || $root!=null){
        while ($root!=null){
            $stk[count($stk)] = $root;
            $root = $root->left;
        }

        $root = array_pop($stk);

        if($prev!=null && $prev ==$pNode){
            return $root;
        }

        $prev = $root;
        $root =$root->right;
    }
    return null;
}