Java/C++ | DFS |  PreorderMirror
TWO DFS Preorder Mirror to each other.\nTWO Pass:\n One path start from left child node first.\n The other path start from right child node first.\n\nWhen they 
### TWO DFS Preorder Mirror to each other.\nTWO Pass:\n* One path start from left child node first.\n* The other path start from right child node first.\n\nWhen they reach to the same node [6] (for example), \nupdate the max level they saw so far. (Does not include current node [6].)\n\nD[root->val] = max(left_max_level, right_max_level)\n\n![image](https://assets.leetcode.com/users/images/23823656-af4b-48a8-a0b6-ad8111f97229_1667190448.0634913.png)\n\n\n\n### 2-Pass DFS preorder:  from left and from right, save max level before current node.\n```\nclass Solution {\npublic:\n    vector<int> D;\n    int lvl_left = 0;\n    int lvl_right = 0;\n    void preorderLeft(TreeNode* root, int level){\n        if (root == nullptr) return;\n        D[root->val] = lvl_left;\n        lvl_left = max(level,lvl_left);\n        preorderLeft(root->left,level+1);\n        preorderLeft(root->right,level+1);\n    }\n    \n    void preorderRight(TreeNode* root, int level){\n        if (root == nullptr) return;\n        D[root->val] = max(D[root->val], lvl_right);\n        lvl_right = max(level,lvl_right);\n        preorderRight(root->right,level+1);\n        preorderRight(root->left,level+1);\n    }\n    \n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        D.resize(100001,0);\n        lvl_left = lvl_right = 0;\n        preorderLeft(root,0); preorderRight(root,0);\n        int sz = queries.size();\n        vector<int> ans(sz,0);\n        int i=0;\n        for(int val : queries) {\n            ans[i++] = D[val];\n        }\n        return ans;\n    } \n};\n```\n\nJava Version\n```\nclass Solution {\n    private static int leftmax;\n    private static int rightmax;\n    private static int[] all_lvl;\n    \n    private void dfsLeft(TreeNode root, int level){\n        if (root==null){\n            return;\n        }\n        all_lvl[root.val] = leftmax;\n        leftmax = Math.max(level,leftmax);\n        dfsLeft(root.left, level+1);\n        dfsLeft(root.right, level+1);\n    }\n    private void dfsRight(TreeNode root, int level){\n        if (root==null){\n            return;\n        }\n        all_lvl[root.val] = Math.max(all_lvl[root.val], rightmax);\n        rightmax= Math.max(level,rightmax);\n        dfsRight(root.right, level+1);\n        dfsRight(root.left, level+1);\n    }\n    \n    public int[] treeQueries(TreeNode root, int[] queries) {\n        leftmax=0;\n        rightmax=0;\n        int n = 100001;\n        all_lvl = new int[n];\n        dfsLeft(root,0);\n        dfsRight(root,0);\n        int m = queries.length;\n        int [] ans = new int[m];\n        for(int i = 0; i < m;i++){\n            ans[i]=all_lvl[queries[i]];\n        }\n        return ans;\n    }\n}\n```\n### Compute Height and Depth, save Top 2 Heights at each level\n\n![image](https://assets.leetcode.com/users/images/0740d0aa-9f5c-4872-9007-ce53acaa65e5_1667191979.9969049.png)\n\n```\nclass Solution {\npublic:\n\n    vector<int> H;\n    vector<int> D;\n    vector<vector<int>> lvl; //O(Height)\n    // compute height and depth of each nodes.\n    int n = 0;\n    int dfs(TreeNode* r, int depth) {\n        if (r == nullptr) return 0;\n        D[r->val] = depth;\n        n = max(n, r->val);\n        int a = dfs(r->left, depth+1);\n        int b = dfs(r->right, depth+1);\n        int h = max(a,b)+1;\n        H[r->val] = h;\n        return h;\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n       \n        // DFS: save height and depth\n        H.resize(100001, 0); //O(N)\n        D.resize(100001, 0);\n        int max_lvl = dfs(root, 0) - 1;\n        \n        // Save Top 2 heights at each level.\n        lvl.resize(max_lvl+1, vector<int>(2, 0));\n        for(int val = 1; val <= n; ++val) {\n            int d = D[val];\n            auto & v = lvl[d];\n            int& a = v[0];\n            int& b = v[1];\n            // keep H[a] <= H[b]\n            if (H[val] > H[a] && H[val] < H[b]) {\n                a = val;\n            } else if (H[val] >= H[b]) {\n                a = b; \n                b = val;\n            }\n        }\n        \n        int i = 0;\n        vector<int> ans(queries.size(), max_lvl);\n        for(auto x: queries) {\n            int lvl_cnt = D[x]; \n            auto& v = lvl[lvl_cnt];\n            // x is the max height, update with 2nd heightest at this level.\n            if (x == v[1]) {\n                ans[i] = lvl_cnt + H[v[0]] - 1;\n            }\n            ++i;\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search']