leetcode100.Same Tree

发表于 更新于 分类于 ，

题目要求

1
传入两棵树的根节点，判断这两棵树是否相同

此题的核心就在于如何遍历树。一旦我们解决了这个问题，题目也就迎刃而解了。
下面就来介绍一下 关于树的一些基本知识

1.预备知识

树（tree）可以用几种方式定义。定义树的一种自然方式是递归的方式。一棵树是一些节点的集合，这个集合可以是空集。若不是空集，则树由叫做根（root）的节点r以及0个或多个非空子树T1，T2…Tk组成，这些子树中每一棵的根都被来自根r的一条有向的边（edge）所连结。

节点的深度： 从根到该节点的唯一的路径的长

二叉树： 一个每个节点都不能有多于两个儿子的树
题目中二叉树的节点表示为

1
2
3
4
5
6
7
8
9
class TreeNode{
     //节点的值
     int val;
     //左子节点，可以为null
     TreeNode left;
     //右子节点，可以为null
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

2.二叉树的遍历方法

中序遍历：首先处理左子树，然后是当前节点，最后处理右子树。这个算法的总的运行时间是O(N)，这是因为在树的每一个节点处进行的工作是常数时间，一共有n个节点，所以运行时间为O(N)

后序遍历：先处理左子树，再处理右子树，然后再处理当前节点。这个遍历算法可以用于场景如，计算一个节点的高度。

先序遍历：先处理当前节点，在处理左子树和右子树

层序遍历：所有深度为d的节点要在深度d+1的节点之前重组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//二叉树的中序遍历 
//递归
void inOrder(TreeNode node){
    if(node!=null){
        inOrder(node.left);
        visit(node);
        inOrder(node.right);
    }
}

//二叉树的中序遍历
//非递归 需要利用栈
void inOrder(TreeNode node){
    Stack<TreeNode> s = new Stack<TreeNode>();
    TreeNode temp = node;
    for( ; ; ){
        //访问左节点
        while(temp!=null){
            s.push(temp);
            temp = temp.left;
        }
        
        //从左节点回来，访问右节点
        if(!s.isEmpty()){
            temp = s.pop();
            //访问当前节点
            System.out.println(temp.val);
            temp = temp.right;
        }else{
            return;
        }
    }
}
//二叉树的后序遍历
void postOrder(TreeNode node){
    if(node!=null){
        postOrder(node.left);
        postOrder(node.right);
        visit(node);
    }
}

//二叉树的前序遍历
void preOrder(TreeNode node){
    if(node!=null){
        visit(node);
        preOrder(node.left);
        preOrder(node.right);
    }
}

##3.本题的解法##

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
**
 * @author rale
 * leetcode100
 * Given two binary trees, write a function to check if they are equal or not.
 * Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
 */
public class SameTree {

    //递归 即当前值和左右子树都相等，则是相同的树，否则不是
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null){
            return q==null?true:false;
        }else if(q==null){
            return p==null?true:false;
        }
        if(p.val == q.val){
            return isSameTree(p.left,q.left)&&isSameTree(p.right, q.right);
        }else{
            return false;
        }
    }
    
    //循环 中序遍历
    public boolean isSameTree2(TreeNode p, TreeNode q){
        Stack<TreeNode> stackP = new Stack<TreeNode>();
        Stack<TreeNode> stackQ = new Stack<TreeNode>();
        if(p!=null){
            stackP.push(p);
        }
        if(q!=null){
            stackQ.push(q);
        }
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            TreeNode tempP = stackP.pop();
            TreeNode tempQ = stackQ.pop();
            if(tempP.val!=tempQ.val){
                return false;
            }
            if(tempP.right!=null){
                stackP.push(tempP.right);
            }
            if(tempQ.right!=null){
                stackQ.push(tempQ.right);
            }
            if(stackP.size()!=stackQ.size()){
                return false;
            }
            if(tempP.left!=null){
                stackP.push(tempP.left);
            }
            if(tempQ.left!=null){
                stackQ.push(tempQ.left);
            }
            if(stackP.size()!=stackQ.size()){
                return false;
            }
        }
        return stackP.size()==stackQ.size();
    }
    
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}