剑指 Offer 26. 树的子结构

桃扇骨 2022-09-10 04:13 97阅读 0赞

> 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
> 
> B是A的子结构， 即 A中有出现和B相同的结构和节点值。
> 
> 例如:  
> 给定的树 A:
> 
> 3  
> / \\  
> 4 5  
> / \\  
> 1 2  
> 给定的树 B：
> 
> 4  
> /  
> 1  
> 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
> 
> 示例 1：
> 
> 输入：A = \[1,2,3\], B = \[3,1\]  
> 输出：false  
> 示例 2：
> 
> 输入：A = \[3,4,5,1,2\], B = \[4,1\]  
> 输出：true  
> 限制：
> 
> 0 <= 节点个数 <= 10000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public boolean Substructure(TreeNode A, TreeNode B){
            // 因为题目约定空树不是任何一个树的子树，所以首先判断A和B是不是空树，
            // 如果是则短路返回false，不判断后边的条件
            // 如果不为空，则判断后边的条件
            // 从根节点开始判断B是否是A的子树，
            // 如果不是，再从A的左节点开始判断B是否是A的子树，
            // 如果不是，再从A的右节点开始判断B是否是A的子树，以此类推进行递归
            // 三个条件只要成立一个，那么B就是A的子树
            return (A != null && B != null) && (recur(A,B) || Substructure(A.left,B) || Substructure(A.right,B));
        }
        public boolean recur(TreeNode A,TreeNode B){
            // 如果 B 已经遍历完，说明 B 与 A 已经匹配完了
            if(B == null){
                return true;
            }
            // 如果 B 没有遍历完，A遍历完到了叶子节点 或者 A 节点的值与 B 不同，说明匹配失败返回
            if(A == null || A.val != B.val){
                return false;
            }
            // 如果 A 与 B 都没有遍历完，且 A 节点的值与 B 节点的值相同，那么继续遍历 A 与 B 的下一个节点
            return recur(A.left,B) && recur(A.right,B);
        }

&&的优先级大于 || 的优先级，所以返回值那里，最好加上括号。可以测试下下面的语句。

System.out.println(false && true || true);
    System.out.println(true || true && false);

--------------------

《自控力》这本书指出：长期睡眠不足让你更容易感到压力、萌生欲望、受到诱惑。你还会很难控制情绪、集中注意力。保持良好的睡眠质量与时间，是提高学习效率的必要条件。