【leetcode】叶子相似的树

叶子相似的树

1、题目描述

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

示例 1：

输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 =[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

2、算法描述

核心思想：
	采用中序遍历思想，把叶子节点一次压如一个栈中，从而只需要比较两个栈是否一样就行

3、代码实现

package com.java;

import com.bean.TreeNode;

import java.util.Stack;

/**
 * @author huangchao
 * @date 2021/5/10
 */
public class Day37_Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Stack stack1 = new Stack<>();
        Stack stack2 = new Stack<>();

        this.findRootNode(root1,stack1);
        this.findRootNode(root2,stack2);
        if (stack1.size() != stack2.size()) {
            return false;
        }

        while (!stack1.isEmpty()) {
            int element = stack1.pop();
            if (element == stack2.peek()) {
                stack2.pop();
            }
            if (stack2.isEmpty()) {
                break;
            }
        }
        return stack2.isEmpty() && stack1.isEmpty();
    }

    //中序遍历找到所有根节点
    public void findRootNode(TreeNode root,Stack stack) {
        if (root != null) {
            findRootNode(root.left,stack);

            if (root.left == null && root.right == null) {
                stack.push(root.val);
            }

            findRootNode(root.right,stack);
        }
    }
}