【1错-1】Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/

image.png

（图片来源https://leetcode.com/problems/leaf-similar-trees/）

日期	是否一次通过	comment
2018-12-15 22:50	2方法看答案后复现两次才成功	preOrder遍历，stack是先right后left；然而读取stack时，最上面的是left，所以读取是先left后right

1. 两棵树分别读取完，再比较：
   遍历获得每个数的叶子节点，再比较结果就好（先序遍历就好了，递归、非递归都方便写）。

2. 先读取完一棵树，再比较：
   2.1. 先对其中一棵树做先序遍历，叶子保存在stack中；
   2.2. 对另一棵树中，分别读取每个叶子节点与stack中的元素比较即可；
   2.3. 注意点：preOrder遍历，stack是先right后left；然而读取stack时，最上面的是left，所以读取是先left后right

3. 两棵树边读边比较：
   3.1. 每次读取到一个叶子节点就立刻返回进行比较；
   3.2. 比较通过再走下一个叶子节点

只读取一棵树

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {

        if(root1 == null || root2 == null) {
            return root1 == root2;
        }
        Stack<Integer> nodeS = new Stack<>();
        extraLeaf(root1, nodeS);
        
        return compTree(nodeS, root2) && nodeS.isEmpty();
    }
    
    private void extraLeaf(TreeNode root, Stack<Integer> nodeS) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            nodeS.push(root.val);
        }
        extraLeaf(root.right, nodeS);
        extraLeaf(root.left, nodeS);
    }
    
    public boolean compTree(Stack<Integer> nodeS, TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.left == null && root.right == null) {
            if(nodeS.isEmpty()) {
                return false;
            } else {
                return nodeS.pop() == root.val;
            }
        }
        return compTree(nodeS, root.left) && compTree(nodeS, root.right); 
    }
}

两棵树边读边比较

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(root1); s2.push(root2);
        while (!s1.empty() && !s2.empty())
            if (dfs(s1) != dfs(s2)) return false;
        return s1.empty() && s2.empty();
    }

    public int dfs(Stack<TreeNode> s) {
        while (true) {
            TreeNode node = s.pop();
            if (node.right != null) s.push(node.right);
            if (node.left != null) s.push(node.left);
            if (node.left == null && node.right == null) return node.val;
        }
    }
}