GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — leet-code/Java/Subtree.java at master · awangdev/leet-code Expand file tree/ Copy pathSubtree.javaMore file actions executable file ·210 lines (179 loc) · 5.47 KB / Copy pathSubtree.javaFile metadata and controlsexecutable file ·210 lines (179 loc) · 5.47 KB 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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 E 1525671122 tags: Tree, DFS 给一个binary tree s, 和一个binary tree t, 检查t是不是s的subtree. #### DFS - 跟 identical binary tree的写法很像 - 只有 current s.val = t.val 的时候才需要compare same tree. - 其他情况, 继续recursively isSubtree - 注意：即使找到T1 == T2, 但很可能只是数字相同（这里不是binary search tree!!）, 而children不同 - 所以同时要继续recursively isSubtree(T1.left, T2) ...etc. ``` /** Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s: 3 / \ 4 5 / \ 1 2 Given tree t: 4 / \ 1 2 Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s: 3 / \ 4 5 / \ 1 2 / 0 Given tree t: 4 / \ 1 2 Return false. */ class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null || t == null) { return s == null && t == null; } return (s.val == t.val && sameTree(s, t)) || isSubtree(s.left, t) || isSubtree(s.right, t); } private boolean sameTree(TreeNode s, TreeNode t) { if (s == null || t == null) { return s == null && t == null; } return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right); } } /* You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. Example T2 is a subtree of T1 in the following case: 1 3 / \ / T1 = 2 3 T2 = 4 / 4 T2 isn't a subtree of T1 in the following case: 1 3 / \ \ T1 = 2 3 T2 = 4 / 4 Note A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical. Tags Expand Recursion Binary Tree */ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ /* Thoughts: similar to compare identical trees. Except: only start compare if s.val == t.val, otherwise, keep dfs. */ class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null || t == null) { return s == null && t == null; } boolean checkSubTree = false; if (s.val == t.val) { checkSubTree = sameTree(s, t); } return checkSubTree || isSubtree(s.left, t) || isSubtree(s.right, t); } private boolean sameTree(TreeNode s, TreeNode t) { if (s == null || t == null) { return s == null && t == null; } return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right); } } /** Previous notes Thoughts: When T2 == null, reardless of T1 == null or NO, it can always return true; WHen T2 != null, T1==null returns false; 1. recursively compare the two nodes: if both null, okay; if everything goes well, get deeper into the child nodes. 2. resursively check subtree: check root.left or root.right comparing with T2. */ public class Solution { /** * @param T1, T2: The roots of binary tree. * @return: True if T2 is a subtree of T1, or false. */ public boolean isSubtree(TreeNode T1, TreeNode T2) { if (T2 == null) { return true; } else if (T1 == null) { return false; } else { return compare(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2); } } //Recursive compare public boolean compare(TreeNode node1, TreeNode node2) { if (node1 == null && node2 == null) { return true; } if (node1 == null || node2 == null){ return false; } if (node1.val != node2.val) { return false; } return compare(node1.left, node2.left) && compare(node1.right, node2.right); } } // 2.22 recap: Find T2 first, then do a divide and conquer compare public class Solution { /** * @param T1, T2: The roots of binary tree. * @return: True if T2 is a subtree of T1, or false. */ public boolean isSubtree(TreeNode T1, TreeNode T2) { if (T1 == null || T2 == null) { return T2 == null; } if (T1.val == T2.val) { return compare(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2); } else { return isSubtree(T1.left, T2) || isSubtree(T1.right, T2); } } public boolean compare(TreeNode T1, TreeNode T2) { if (T1 == null && T2 == null) { return true; } else if (T1 == null || T2 == null) { return false; } if (T1.val != T2.val) { return false; } return compare(T1.left, T2.left) && compare(T1.right, T2.right); } } ``` |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |